Maximum coin collection

Array Dynamic Programming

52.8% acceptance

Mar 31, 2026

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_coins(lane1: Vec<i32>, lane2: Vec<i32>) -> i64 {
    let n = lane1.len();
    // dp[i][state]: max coins ending at mile i with `state` switches used so far
    // state 0: in lane1, 0 switches
    // state 1: in lane2, 1 switch (switched from lane1 to lane2)
    // state 2: in lane1, 2 switches (switched back to lane1)
    // We can enter at any mile, so we take max(dp[i][state], lane_value) at each step.
    
    let neg = i64::MIN / 2;
    // dp[0] = in lane1, 0 switches
    // dp[1] = in lane2, 1 switch
    // dp[2] = in lane1, 2 switches
    let mut dp = [neg; 3];
    let mut ans = neg;
    
    for i in 0..n {
      let l1 = lane1[i] as i64;
      let l2 = lane2[i] as i64;
      
      let new0 = l1.max(dp[0] + l1);
      let new1 = (dp[0] + l2).max(if dp[1] == neg { neg } else { dp[1] + l2 }).max(l2);
      let new2 = (dp[1] + l1).max(if dp[2] == neg { neg } else { dp[2] + l1 });
      
      dp[0] = new0;
      dp[1] = new1;
      dp[2] = new2;
      
      ans = ans.max(dp[0]).max(dp[1]).max(dp[2]);
    }
    
    ans
  }
}