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 and lane1[i] > 0, Mario gains lane1[i] coins.
  • If Mario is in lane 1 at mile i and lane1[i] < 0, Mario pays a toll and loses abs(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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input: lane1 = [1,-2,-10,3], lane2 = [-5,10,0,1]

Output: 14

Explanation:

Mario drives the first mile on lane 1.
He then changes to lane 2 and drives for two miles.
He changes back to lane 1 for the last mile.
Mario collects 1 + 10 + 0 + 3 = 14 coins.

Example 2

1
2
3
4
5
6
7
8
9

Input: lane1 = [1,-1,-1,-1], lane2 = [0,3,4,-5]

Output: 8

Explanation:

Mario starts at mile 0 in lane 1 and drives one mile.
He then changes to lane 2 and drives for two more miles. He exits the freeway before mile 3.
He collects 1 + 3 + 4 = 8 coins.

Example 3

1
2
3
4
5
6
7
8

Input: lane1 = [-5,-4,-3], lane2 = [-1,2,3]

Output: 5

Explanation:

Mario enters at mile 1 and immediately switches to lane 2. He stays here the entire way.
He collects a total of 2 + 3 = 5 coins.

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

  1. Initialize a variable to track the maximum sum ending at the current position (cur) and the overall maximum (ans).
  2. Iterate through the array:
    • For each coin value, update cur as the maximum of the current coin or cur + coin.
    • Update ans as the maximum of ans and cur.
  3. Return ans as the result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int maxCoins(vector<int>& coins) {
        int ans = coins[0], cur = coins[0];
        for (int i = 1; i < coins.size(); ++i) {
            cur = max(coins[i], cur + coins[i]);
            ans = max(ans, cur);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int maxCoins(int[] coins) {
        int ans = coins[0], cur = coins[0];
        for (int i = 1; i < coins.length; ++i) {
            cur = Math.max(coins[i], cur + coins[i]);
            ans = Math.max(ans, cur);
        }
        return ans;
    }
}
1
2
3
4
5
6
7

class Solution:
    def maxCoins(self, coins: list[int]) -> int:
        ans = cur = coins[0]
        for c in coins[1:]:
            cur = max(c, cur + c)
            ans = max(ans, cur)
        return ans

Complexity

  • ⏰ Time complexity: O(n), since we process each element once.
  • 🧺 Space complexity: O(1), only a constant number of variables are used.