Best Time to Buy and Sell Stock II
Best Time to Buy and Sell Stock II is a medium dynamic programming problem solved with the state machine dp - stock problems pattern.
The best approach, greedy (sum every rise), runs in O(n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from state machine dp up.
Problem
Same prices, but now you may make as many transactions as you like. You can hold at most one share at a time (sell before you buy again). Return the maximum profit.
Examples
Example 1
- Input
prices = [7, 1, 5, 3, 6, 4]- Output
7- Why
- Buy 1 sell 5 (+4), buy 3 sell 6 (+3).
Example 2
- Input
prices = [1, 2, 3, 4, 5]- Output
4
Constraints
1 <= prices.length <= 3 * 10^4.- Unlimited transactions, holding at most one share at a time.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 9 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| State machine DP | O(n) | O(1) |
| Greedy (sum every rise) | O(n) | O(1) |
1State machine DP
O(n)O(1)hold = best profit while holding a share; free = best profit while not holding. Each day: hold = max(hold, free - price); free = max(free, hold + price).
- hold = -prices[0], free = 0.
- Update both each day (use the old hold when computing free).
class Solution {
public int maxProfit(int[] prices) {
int hold = -prices[0], free = 0;
for (int i = 1; i < prices.length; i++) {
int newHold = Math.max(hold, free - prices[i]);
free = Math.max(free, hold + prices[i]);
hold = newHold;
}
return free;
}
}class Solution:
def maxProfit(self, prices: List[int]) -> int:
hold, free = -prices[0], 0
for i in range(1, len(prices)):
newHold = max(hold, free - prices[i])
free = max(free, hold + prices[i])
hold = newHold
return freeclass Solution {
public:
int maxProfit(vector<int>& prices) {
int hold = -prices[0], free = 0;
for (int i = 1; i < (int)prices.size(); i++) {
int newHold = max(hold, free - prices[i]);
free = max(free, hold + prices[i]);
hold = newHold;
}
return free;
}
};function maxProfit(prices) {
let hold = -prices[0], free = 0;
for (let i = 1; i < prices.length; i++) {
const newHold = Math.max(hold, free - prices[i]);
free = Math.max(free, hold + prices[i]);
hold = newHold;
}
return free;
}2Greedy (sum every rise)
O(n)O(1)Any profitable stretch can be split into day-to-day rises. Collecting every positive difference gives the same total.
- profit += max(0, prices[i] - prices[i - 1]).
class Solution {
public int maxProfit(int[] prices) {
int profit = 0;
for (int i = 1; i < prices.length; i++) profit += Math.max(0, prices[i] - prices[i - 1]);
return profit;
}
}class Solution:
def maxProfit(self, prices: List[int]) -> int:
profit = 0
for i in range(1, len(prices)):
profit += max(0, prices[i] - prices[i - 1])
return profitclass Solution {
public:
int maxProfit(vector<int>& prices) {
int profit = 0;
for (int i = 1; i < (int)prices.size(); i++) profit += max(0, prices[i] - prices[i - 1]);
return profit;
}
};function maxProfit(prices) {
let profit = 0;
for (let i = 1; i < prices.length; i++) profit += Math.max(0, prices[i] - prices[i - 1]);
return profit;
}Edge cases to test
- Strictly falling prices (0)
Hints
Hint 1
Two states each day: holding a share or not. Or: every upward step can be collected.
FAQ
What is the best time complexity for Best Time to Buy and Sell Stock II?
Greedy (sum every rise) runs in O(n) time and O(1) extra space.
Which pattern does Best Time to Buy and Sell Stock II use?
It is a dynamic programming problem that uses the state machine dp - stock problems pattern. Other problems with the same pattern: Best Time to Buy and Sell Stock, Best Time to Buy and Sell Stock with Transaction Fee, Best Time to Buy and Sell Stock with Cooldown.
Is there a brute force solution for Best Time to Buy and Sell Stock II?
Yes. State machine DP takes O(n) time and O(1) space. hold = best profit while holding a share; free = best profit while not holding.
Which edge cases should I test for Best Time to Buy and Sell Stock II?
Strictly falling prices (0).