1class Solution {
2    private int n; // Length of the lanes
3    private int[] lane1; // Coins in lane1
4    private int[] lane2; // Coins in lane2
5    private Long[][][] f; // Memoization table to store intermediate results
6
7    public long maxCoins(int[] lane1, int[] lane2) {
8        this.n = lane1.length; // Initialize the lanes' length
9        this.lane1 = lane1; // Assign lane1 coins
10        this.lane2 = lane2; // Assign lane2 coins
11        this.f = new Long[n][2][3]; // Create memoization table with dimensions
12        long maxCoins = Long.MIN_VALUE; // Initialize the maximum coins collected
13      
14        // Iterate over each starting position in lane1
15        for (int i = 0; i < n; ++i) {
16            maxCoins = Math.max(maxCoins, dfs(i, 0, 2)); // Maximize coins collected
17        }
18      
19        return maxCoins; // Return the max coins that can be collected
20    }
21
22    // Recursive function to calculate the max coins dynamically
23    private long dfs(int index, int lane, int remainingSwitches) {
24        if (index >= n) { // Base case: If index out of bounds, return 0
25            return 0;
26        }
27        if (f[index][lane][remainingSwitches] != null) { // Return cached result
28            return f[index][lane][remainingSwitches];
29        }
30      
31        int coinsAtCurrent = (lane == 0) ? lane1[index] : lane2[index]; // Coins at current position
32      
33        // Select max coins between staying on the same lane or switching
34        long maxCoinsCollected = Math.max(coinsAtCurrent, 
35                                          dfs(index + 1, lane, remainingSwitches) + coinsAtCurrent);
36      
37        // Check possibilities if we have remaining switches
38        if (remainingSwitches > 0) {
39            // Switch lanes and collect coins, or switch without collecting
40            maxCoinsCollected = Math.max(maxCoinsCollected, 
41                                         dfs(index + 1, lane ^ 1, remainingSwitches - 1) + coinsAtCurrent);
42            maxCoinsCollected = Math.max(maxCoinsCollected, 
43                                         dfs(index, lane ^ 1, remainingSwitches - 1));
44        }
45      
46        // Cache and return the calculated result
47        return f[index][lane][remainingSwitches] = maxCoinsCollected;
48    }
49}
50

1class Solution {
2public:
3    long long maxCoins(vector<int>& lane1, vector<int>& lane2) {
4        int n = lane1.size(); // Get the number of elements in each lane.
5        long long answer = -1e18; // Initialize the answer with a very large negative number.
6      
7        // Create a 3D vector for memoization initialized with the large negative number.
8        vector<vector<vector<long long>>> memo(n, vector<vector<long long>>(2, vector<long long>(3, -1e18)));
9
10        // Define a recursive function using lambda for Depth First Search (DFS).
11        auto dfs = [&](auto&& self, int index, int lane, int swapsLeft) -> long long {
12            if (index >= n) {
13                return 0LL; // Base case: If index is out of bounds, no more coins can be collected.
14            }
15          
16            // If we have already computed this state, return the stored value.
17            if (memo[index][lane][swapsLeft] != -1e18) {
18                return memo[index][lane][swapsLeft];
19            }
20          
21            int currentCoin = lane == 0 ? lane1[index] : lane2[index]; // Get the coin value from the current lane.
22          
23            // Calculate the maximum coins by continuing in the same lane.
24            long long maxCoins = max((long long)currentCoin, self(self, index + 1, lane, swapsLeft) + currentCoin);
25          
26            // If we have swaps left, consider switching lanes.
27            if (swapsLeft > 0) {
28                // Try switching lanes at the next step, or right now.
29                maxCoins = max(maxCoins, self(self, index + 1, lane ^ 1, swapsLeft - 1) + currentCoin);
30                maxCoins = max(maxCoins, self(self, index, lane ^ 1, swapsLeft - 1));
31            }
32          
33            // Save the computed value for future use and return it.
34            return memo[index][lane][swapsLeft] = maxCoins;
35        };
36
37        // Try starting from every possible starting position in lane1 or lane2.
38        for (int i = 0; i < n; ++i) {
39            answer = max(answer, dfs(dfs, i, 0, 2)); // Start from lane1.
40        }
41
42        return answer; // Return the maximum coins that can be collected.
43    }
44};
45

1// Define a function `maxCoins` that computes the maximum number of coins collected from two lanes.
2// `lane1` and `lane2` represent arrays of coins in each respective lane.
3function maxCoins(lane1: number[], lane2: number[]): number {
4    const n = lane1.length; // Length of the lanes, assuming both have equal length.
5    const NEG_INF = -1e18; // A constant representing negative infinity for initialization.
6
7    // Create a 3D array 'f' to store computed results for dynamic programming.
8    // Dimensions: n x 2 x 3, initialized with NEG_INF.
9    const f: number[][][] = Array.from({ length: n }, () =>
10        Array.from({ length: 2 }, () => Array(3).fill(NEG_INF))
11    );
12
13    // Define a recursive function 'dfs' with memoization to explore all paths.
14    // This function takes the index `i`, lane `j`, and remaining switches `k`.
15    const dfs = (dfs: Function, i: number, j: number, k: number): number => {
16        if (i >= n) { // Boundary condition: If index exceeds bounds, return 0.
17            return 0;
18        }
19        if (f[i][j][k] !== NEG_INF) { // If already computed, return the stored value.
20            return f[i][j][k];
21        }
22
23        const x = j === 0 ? lane1[i] : lane2[i]; // Current coin value based on the lane.
24        // Calculate the max coins collected by either picking the current or moving forward without switching.
25        let ans = Math.max(x, dfs(dfs, i + 1, j, k) + x);
26
27        if (k > 0) { // If switches are available, explore switching lanes.
28            ans = Math.max(ans, dfs(dfs, i + 1, j ^ 1, k - 1) + x); // Switch and collect current.
29            ans = Math.max(ans, dfs(dfs, i, j ^ 1, k - 1)); // Switch without collecting current.
30        }
31
32        f[i][j][k] = ans; // Memoize the result.
33        return ans;
34    };
35
36    let ans = NEG_INF; // Variable to keep track of the maximum result.
37  
38    // Initiate DFS from both lanes at each position with 2 switches.
39    for (let i = 0; i < n; ++i) {
40        ans = Math.max(ans, dfs(dfs, i, 0, 2)); // Start from lane 1.
41    }
42
43    return ans; // Return the maximum number of coins collected.
44}
45