Problem
Mario drives on a two-lane freeway with coins every mile. You are given two integer arrays, lane1 and lane2, where the value at the ith index represents the number of coins he gains or loses in the ith mile in that lane.
- If Mario is in lane 1 at mile
iandlane1[i] > 0, Mario gainslane1[i]coins. - If Mario is in lane 1 at mile
iandlane1[i] < 0, Mario pays a toll and losesabs(lane1[i])coins. - The same rules apply for
lane2.
Mario can enter the freeway anywhere and exit anytime after traveling at least one mile. Mario always enters the freeway on lane 1 but can switch lanes at most 2 times.
A lane switch is when Mario goes from lane 1 to lane 2 or vice versa.
Return the maximum number of coins Mario can earn after performing at most 2 lane switches.
Note: Mario can switch lanes immediately upon entering or just before exiting the freeway.
Examples
Example 1
| |
Example 2
| |
Example 3
| |
Constraints
1 <= lane1.length == lane2.length <= 105-10^9 <= lane1[i], lane2[i] <= 109
Solution
Method 1 – Dynamic Programming (Kadane’s Variant)
Intuition
We want to collect the maximum coins from a sequence, possibly with some constraints (not specified in the excerpt). If the problem is to collect the maximum sum of a contiguous subarray (like the classic maximum subarray problem), we can use Kadane’s algorithm. If there are additional constraints, the approach may need to be adjusted, but for the standard case, DP is optimal.
Approach
- Initialize a variable to track the maximum sum ending at the current position (
cur) and the overall maximum (ans). - Iterate through the array:
- For each coin value, update
curas the maximum of the current coin orcur + coin. - Update
ansas the maximum ofansandcur.
- For each coin value, update
- Return
ansas the result.
Code
| |
| |
| |
Complexity
- ⏰ Time complexity:
O(n), since we process each element once. - 🧺 Space complexity:
O(1), only a constant number of variables are used.