Skip to content

3466. Maximum Coin Collection

Approach 1: 1D DP

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  long long maxCoins(vector<int>& lane1, vector<int>& lane2) {
    const int n = lane1.size();
    // dp[i][k] := the maximum number of coins at i-th mile with k switches
    vector<vector<long>> dp(n, vector<long>(3, LONG_MIN));
    dp[0][0] = lane1[0];
    dp[0][1] = lane2[0];

    for (int i = 1; i < n; ++i) {
      dp[i][0] = max(0L, dp[i - 1][0]) + lane1[i];
      dp[i][1] = max({0L, dp[i - 1][0], dp[i - 1][1]}) + lane2[i];
      dp[i][2] = max(dp[i - 1][1], dp[i - 1][2]) + lane1[i];
    }

    return accumulate(dp.begin(), dp.end(), LONG_MIN,
                      [](long acc, const vector<long>& row) {
      return max(acc, ranges::max(row));
    });
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
  public long maxCoins(int[] lane1, int[] lane2) {
    final int n = lane1.length;
    // dp[i][k] := the maximum number of coins at i-th mile with k switches
    long[][] dp = new long[n][3];
    Arrays.stream(dp).forEach(A -> Arrays.fill(A, Long.MIN_VALUE));
    dp[0][0] = lane1[0];
    dp[0][1] = lane2[0];

    for (int i = 1; i < n; ++i) {
      dp[i][0] = Math.max(0, dp[i - 1][0]) + lane1[i];
      dp[i][1] = Math.max(0, Math.max(dp[i - 1][0], dp[i - 1][1])) + lane2[i];
      dp[i][2] = Math.max(dp[i - 1][1], dp[i - 1][2]) + lane1[i];
    }

    return Arrays.stream(dp).flatMapToLong(Arrays::stream).max().getAsLong();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
  def maxCoins(self, lane1: list[int], lane2: list[int]) -> int:
    n = len(lane1)
    # dp[i][k] := the maximum number of coins at i-th mile with k switches
    dp = [[-math.inf] * 3 for _ in range(n)]
    dp[0][0] = lane1[0]
    dp[0][1] = lane2[0]

    for i in range(1, n):
      dp[i][0] = max(0, dp[i - 1][0]) + lane1[i]
      dp[i][1] = max(0, dp[i - 1][0], dp[i - 1][1]) + lane2[i]
      dp[i][2] = max(dp[i - 1][1], dp[i - 1][2]) + lane1[i]

    return max(map(max, dp))

Approach 2: $O(1)$ DP

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  long long maxCoins(vector<int>& lane1, vector<int>& lane2) {
    // dp[k] := the maximum number of coins at mile so far with k switches
    vector<long> dp = {lane1[0], lane2[0], LONG_MIN};
    long ans = ranges::max(dp);

    for (int i = 1; i < lane1.size(); ++i) {
      dp = {max(0L, dp[0]) + lane1[i],           //
            max({0L, dp[0], dp[1]}) + lane2[i],  //
            max(dp[1], dp[2]) + lane1[i]};
      ans = max(ans, ranges::max(dp));
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
  public long maxCoins(int[] lane1, int[] lane2) {
    // dp[k] := the maximum number of coins at mile so far with k switches
    long[] dp = {lane1[0], lane2[0], Long.MIN_VALUE};
    long ans = Math.max(dp[0], dp[1]);

    for (int i = 1; i < lane1.length; ++i) {
      dp = new long[] {Math.max(0, dp[0]) + lane1[i],                  //
                       Math.max(Math.max(0, dp[0]), dp[1]) + lane2[i], //
                       Math.max(dp[1], dp[2]) + lane1[i]};
      ans = Math.max(ans, Math.max(Math.max(dp[0], dp[1]), dp[2]));
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def maxCoins(self, lane1: list[int], lane2: list[int]) -> int:
    # dp[k] := the maximum number of coins at mile so far with k switches
    dp = (lane1[0], lane2[0], -math.inf)
    ans = max(dp)

    for i in range(1, len(lane1)):
      dp = (max(0, dp[0]) + lane1[i],
            max(0, dp[0], dp[1]) + lane2[i],
            max(dp[1], dp[2]) + lane1[i])
      ans = max(ans, max(dp))

    return ans