Problem

Example 1:

Solution

Method 1 – Dynamic Programming (Kadane’s Variant)

Intuition

We want to collect the maximum coins from a sequence, possibly with some constraints (not specified in the excerpt). If the problem is to collect the maximum sum of a contiguous subarray (like the classic maximum subarray problem), we can use Kadane’s algorithm. If there are additional constraints, the approach may need to be adjusted, but for the standard case, DP is optimal.

Approach

  1. Initialize a variable to track the maximum sum ending at the current position (cur) and the overall maximum (ans).
  2. Iterate through the array:
    • For each coin value, update cur as the maximum of the current coin or cur + coin.
    • Update ans as the maximum of ans and cur.
  3. Return ans as the result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int maxCoins(vector<int>& coins) {
        int ans = coins[0], cur = coins[0];
        for (int i = 1; i < coins.size(); ++i) {
            cur = max(coins[i], cur + coins[i]);
            ans = max(ans, cur);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int maxCoins(int[] coins) {
        int ans = coins[0], cur = coins[0];
        for (int i = 1; i < coins.length; ++i) {
            cur = Math.max(coins[i], cur + coins[i]);
            ans = Math.max(ans, cur);
        }
        return ans;
    }
}
1
2
3
4
5
6
7

class Solution:
    def maxCoins(self, coins: list[int]) -> int:
        ans = cur = coins[0]
        for c in coins[1:]:
            cur = max(c, cur + c)
            ans = max(ans, cur)
        return ans

Complexity

  • ⏰ Time complexity: O(n), since we process each element once.
  • 🧺 Space complexity: O(1), only a constant number of variables are used.