Skip to content

3466. Maximum Coin Collection πŸ”’

Description

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.

 

Example 1:

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:

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:

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.

Example 4:

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

Output: 11

Explanation:

  • Mario starts at the beginning of the freeway and immediately switches to lane 2. He stays here the whole way.

He collects a total of 9 + (-2) + 4 = 11 coins.

Example 5:

Input: lane1 = [-10], lane2 = [-2]

Output: -2

Explanation:

  • Since Mario must ride on the freeway for at least one mile, he rides just one mile in lane 2.

He collects a total of -2 coins.

 

Constraints:

  • 1 <= lane1.length == lane2.length <= 105
  • -109 <= lane1[i], lane2[i] <= 109

Solutions

We design a function \(\textit{dfs}(i, j, k)\), which represents the maximum number of coins Mario can collect starting from position \(i\), currently on lane \(j\), with \(k\) lane changes remaining. The answer is the maximum value of \(\textit{dfs}(i, 0, 2)\) for all \(i\).

The function \(\textit{dfs}(i, j, k)\) is calculated as follows:

  • If \(i \geq n\), it means Mario has reached the end, return 0;
  • If no lane change is made, Mario can drive 1 mile, then exit, or continue driving, taking the maximum of the two, i.e., \(\max(x, \textit{dfs}(i + 1, j, k) + x)\);
  • If a lane change is possible, there are two choices: drive 1 mile and then change lanes, or change lanes directly, taking the maximum of these two cases, i.e., \(\max(\textit{dfs}(i + 1, j \oplus 1, k - 1) + x, \textit{dfs}(i, j \oplus 1, k - 1))\).
  • Where \(x\) represents the number of coins at the current position.

To avoid repeated calculations, we use memoized search to store the results that have already been computed.

Time complexity is \(O(n)\), and space complexity is \(O(n)\). Where \(n\) represents the length of the lanes.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def maxCoins(self, lane1: List[int], lane2: List[int]) -> int:
        @cache
        def dfs(i: int, j: int, k: int) -> int:
            if i >= n:
                return 0
            x = lane1[i] if j == 0 else lane2[i]
            ans = max(x, dfs(i + 1, j, k) + x)
            if k > 0:
                ans = max(ans, dfs(i + 1, j ^ 1, k - 1) + x)
                ans = max(ans, dfs(i, j ^ 1, k - 1))
            return ans

        n = len(lane1)
        ans = -inf
        for i in range(n):
            ans = max(ans, dfs(i, 0, 2))
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    private int n;
    private int[] lane1;
    private int[] lane2;
    private Long[][][] f;

    public long maxCoins(int[] lane1, int[] lane2) {
        n = lane1.length;
        this.lane1 = lane1;
        this.lane2 = lane2;
        f = new Long[n][2][3];
        long ans = Long.MIN_VALUE;
        for (int i = 0; i < n; ++i) {
            ans = Math.max(ans, dfs(i, 0, 2));
        }
        return ans;
    }

    private long dfs(int i, int j, int k) {
        if (i >= n) {
            return 0;
        }
        if (f[i][j][k] != null) {
            return f[i][j][k];
        }
        int x = j == 0 ? lane1[i] : lane2[i];
        long ans = Math.max(x, dfs(i + 1, j, k) + x);
        if (k > 0) {
            ans = Math.max(ans, dfs(i + 1, j ^ 1, k - 1) + x);
            ans = Math.max(ans, dfs(i, j ^ 1, k - 1));
        }
        return f[i][j][k] = ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    long long maxCoins(vector<int>& lane1, vector<int>& lane2) {
        int n = lane1.size();
        long long ans = -1e18;
        vector<vector<vector<long long>>> f(n, vector<vector<long long>>(2, vector<long long>(3, -1e18)));
        auto dfs = [&](this auto&& dfs, int i, int j, int k) -> long long {
            if (i >= n) {
                return 0LL;
            }
            if (f[i][j][k] != -1e18) {
                return f[i][j][k];
            }
            int x = j == 0 ? lane1[i] : lane2[i];
            long long ans = max((long long) x, dfs(i + 1, j, k) + x);
            if (k > 0) {
                ans = max(ans, dfs(i + 1, j ^ 1, k - 1) + x);
                ans = max(ans, dfs(i, j ^ 1, k - 1));
            }
            return f[i][j][k] = ans;
        };
        for (int i = 0; i < n; ++i) {
            ans = max(ans, dfs(i, 0, 2));
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
func maxCoins(lane1 []int, lane2 []int) int64 {
    n := len(lane1)
    f := make([][2][3]int64, n)
    for i := range f {
        for j := range f[i] {
            for k := range f[i][j] {
                f[i][j][k] = -1
            }
        }
    }
    var dfs func(int, int, int) int64
    dfs = func(i, j, k int) int64 {
        if i >= n {
            return 0
        }
        if f[i][j][k] != -1 {
            return f[i][j][k]
        }
        x := int64(lane1[i])
        if j == 1 {
            x = int64(lane2[i])
        }
        ans := max(x, dfs(i+1, j, k)+x)
        if k > 0 {
            ans = max(ans, dfs(i+1, j^1, k-1)+x)
            ans = max(ans, dfs(i, j^1, k-1))
        }
        f[i][j][k] = ans
        return ans
    }
    ans := int64(-1e18)
    for i := range lane1 {
        ans = max(ans, dfs(i, 0, 2))
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function maxCoins(lane1: number[], lane2: number[]): number {
    const n = lane1.length;
    const NEG_INF = -1e18;
    const f: number[][][] = Array.from({ length: n }, () =>
        Array.from({ length: 2 }, () => Array(3).fill(NEG_INF)),
    );
    const dfs = (dfs: Function, i: number, j: number, k: number): number => {
        if (i >= n) {
            return 0;
        }
        if (f[i][j][k] !== NEG_INF) {
            return f[i][j][k];
        }
        const x = j === 0 ? lane1[i] : lane2[i];
        let ans = Math.max(x, dfs(dfs, i + 1, j, k) + x);
        if (k > 0) {
            ans = Math.max(ans, dfs(dfs, i + 1, j ^ 1, k - 1) + x);
            ans = Math.max(ans, dfs(dfs, i, j ^ 1, k - 1));
        }
        f[i][j][k] = ans;
        return ans;
    };
    let ans = NEG_INF;
    for (let i = 0; i < n; ++i) {
        ans = Math.max(ans, dfs(dfs, i, 0, 2));
    }
    return ans;
}

Comments