Best Time to Buy And Sell Stock II
The briefingthe full drill, in my own words
The drill: Maximize total profit from a price series when you can buy and sell as many times as you like, one share at a time, never holding more than one share at once.
A series of daily stock prices arrives, and the task is to walk away with the maximum total profit possible — buying and selling as many separate times as you like.
Only one share can be held at any moment: a share has to be sold before another one is bought, so overlapping holdings are never allowed.
There's no penalty or cost attached to each individual transaction, so chaining together many small trades is exactly as free as making one long one.
- the price series holds up to a few thousand days
- prices are non-negative integers, zero included
- unlimited transactions are allowed, one share held at a time
- no transaction fees or cooldowns apply on this course
The hintstake only what you need
HINT 1 THE NUDGE
Trying every possible combination of buy and sell days finds the answer, but the number of combinations explodes with every extra day. What does holding a share on day i actually depend on?
HINT 2 THE STRUCTURE
Since a full round trip is always allowed between any two days, ask a smaller question: is tomorrow's price higher than today's? Every such rise is profit you're allowed to bank.
HINT 3 ONE STEP FROM THE ANSWER
Sum up every positive difference between consecutive days — buy the moment before each rise, sell right after it. Chaining every small rise together matches any longer single trade you could have made instead.
Coach's boardthe pattern, step by step
prices = [7, 1, 5, 3, 6, 4]. Sum every positive day-to-day rise — that equals the max profit with unlimited trades.
The splitstwo paces, two languages
class Solution:
def maxProfit(self, prices: List[int]) -> int:
profit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i - 1]:
profit += prices[i] - prices[i - 1]
return profitclass Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
def dfs(day: int, holding: bool) -> int:
if day == n:
return 0
skip = dfs(day + 1, holding)
if holding:
sell = prices[day] + dfs(day + 1, False)
return max(skip, sell)
else:
buy = -prices[day] + dfs(day + 1, True)
return max(skip, buy)
return dfs(0, False)class Solution {
public int maxProfit(int[] prices) {
int profit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) {
profit += prices[i] - prices[i - 1];
}
}
return profit;
}
}class Solution {
public int maxProfit(int[] prices) {
return dfs(prices, 0, false);
}
private int dfs(int[] prices, int day, boolean holding) {
if (day == prices.length) {
return 0;
}
int skip = dfs(prices, day + 1, holding);
if (holding) {
int sell = prices[day] + dfs(prices, day + 1, false);
return Math.max(skip, sell);
} else {
int buy = -prices[day] + dfs(prices, day + 1, true);
return Math.max(skip, buy);
}
}
}✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED