We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Coin Collection

Number: 3806

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Mario is driving along a freeway that has two lanes. Every mile, there is a coin value (which could be positive or negative) on each lane. Mario must ride at least one mile. He always enters on lane 1 but is allowed to switch lanes at most 2 times during his ride. A lane switch can be done immediately upon entering, during the ride, or even right before exiting. The goal is to choose where to enter, when (and if) to switch lanes, and when to exit (i.e. choose a contiguous segment of miles) so that the total coin collection is maximized.

Key Insights

  • This is a contiguous subarray problem with an extra state: the current lane and number of lane switches used.
  • Mario must start in lane 1 if he does not switch immediately; switching immediately (before collecting any coins) is allowed, but it counts as one switch.
  • We can use dynamic programming across the freeway miles while tracking at most 2 lane switches.
  • At each mile, from the current state (lane and switch count), Mario has two possibilities: continue on the same lane or switch lanes (if he hasn’t switched twice already) and then add the coin value of the new lane.
  • A new subarray (ride) can be started at any mile; however, the starting choice is constrained by the rule that the ride must begin on lane 1 (or, by immediately switching, on lane 2 using 1 switch).

Space and Time Complexity

Time Complexity: O(n), where n is the length of the lanes. Space Complexity: O(1) extra space (we only need to maintain DP states for 3 switch counts and 2 lanes).

Solution

We solve this problem using dynamic programming. We define our DP state as:

dp[i][s][l] = maximum coin total ending at mile i when Mario is in lane l (l = lane1 or lane2) and has used s lane switches.

Because the ride is contiguous and Mario may start at any mile, we incorporate the “start new” option into the recurrence. Note that if we start a new segment at a mile i, the following must hold:

  • If starting on lane 1, the switch count must be 0.
  • If starting on lane 2, it means Mario immediately switched upon entering, so the switch count is 1.

For each subsequent mile we update our DP states:

For lane1 with s switches (s = 0, 1, 2):

  • Continue on lane1: dp1[s] = previous dp1[s] + lane1[i]
  • Or (if s > 0) switch from lane2: dp1[s] = previous dp2[s - 1] + lane1[i]
  • If starting a new ride at mile i and s == 0, consider just lane1[i].

For lane2 with s switches:

  • Continue on lane2: dp2[s] = previous dp2[s] + lane2[i]
  • Or (if s > 0) switch from lane1: dp2[s] = previous dp1[s - 1] + lane2[i]
  • If starting a new ride at mile i and s == 1 (i.e. immediate switch), consider just lane2[i].

We update these states mile by mile and maintain the maximum result over all states. The careful tracking of the number of switches and considering “start new” at any mile is the key idea that allows the algorithm to decide whether to continue a ride or begin a new segment for a better outcome.

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java. Each version uses clear variable names and inline comments to explain each step.

# Python solution

import math

def maxCoinCollection(lane1, lane2):
    n = len(lane1)
    # We have 3 possible switch counts: 0, 1, 2.
    # Initialize dp values for lane1 and lane2 for the previous mile.
    # Using -infinity to represent an impossible state.
    NEG_INF = -10**18  
    dp1 = [NEG_INF, NEG_INF, NEG_INF]
    dp2 = [NEG_INF, NEG_INF, NEG_INF]
    
    # At the starting mile (index 0):
    # Option 1: Start on lane 1 with 0 switches.
    dp1[0] = lane1[0]
    # Option 2: Start with an immediate switch to lane 2 (costs 1 switch).
    dp2[1] = lane2[0]
    
    max_coins = max(dp1[0], dp2[1])
    
    # Iterate over miles from 1 to n-1
    for i in range(1, n):
        new_dp1 = [NEG_INF, NEG_INF, NEG_INF]
        new_dp2 = [NEG_INF, NEG_INF, NEG_INF]
        
        for s in range(3):
            # Update lane1 states if continuing from previous mile.
            if dp1[s] != NEG_INF:
                new_dp1[s] = max(new_dp1[s], dp1[s] + lane1[i])
            # Transition: if we were in lane2 and can switch to lane1 (using one extra switch)
            if s > 0 and dp2[s - 1] != NEG_INF:
                new_dp1[s] = max(new_dp1[s], dp2[s - 1] + lane1[i])
                
            # Update lane2 states if continuing on lane2.
            if dp2[s] != NEG_INF:
                new_dp2[s] = max(new_dp2[s], dp2[s] + lane2[i])
            # Transition: if we were in lane1 and can switch to lane2 (using one extra switch)
            if s > 0 and dp1[s - 1] != NEG_INF:
                new_dp2[s] = max(new_dp2[s], dp1[s - 1] + lane2[i])
        
        # Consider starting a new ride at segment i.
        # If starting on lane1, we must start with 0 switches.
        new_dp1[0] = max(new_dp1[0], lane1[i])
        # If starting on lane2, we count an immediate switch: switch count == 1.
        new_dp2[1] = max(new_dp2[1], lane2[i])
        
        # Update overall maximum
        current_max = max(new_dp1 + new_dp2)
        max_coins = max(max_coins, current_max)
        
        # Update dp for next iteration.
        dp1, dp2 = new_dp1, new_dp2
        
    return max_coins

# Example usage:
if __name__ == "__main__":
    # Example 1
    lane1 = [1,-2,-10,3]
    lane2 = [-5,10,0,1]
    print(maxCoinCollection(lane1, lane2))  # Expected output: 14
← Back to All Questions