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
i
andlane1[i] > 0
, Mario gainslane1[i]
coins. - If Mario is in lane 1 at mile
i
andlane1[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
-109 <= 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
cur
as the maximum of the current coin orcur + coin
. - Update
ans
as the maximum ofans
andcur
.
- For each coin value, update
- Return
ans
as 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.