Search for a command to run...
What it teaches: With unlimited transactions, collect every upward step.
Practise it on judges as “Best Time to Buy and Sell Stock II”.
You may buy and sell any number of times (holding at most one share). Return the maximum profit.
Example 1
Input: prices = [7,1,5,3,6,4] Output: 7
Constraints
Pattern clues in the wording
These clues point to Greedy Choice: Make the best-looking choice at each step and never undo it, after proving that this choice is always safe.
Stuck? Take one hint at a time
class Solution {
public int maxProfit(int[] prices) {
return 0;
}
}Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.
Test cases
| # | Input | Expected |
|---|---|---|
| 1 | prices = [7,1,5,3,6,4] | 7 |
| 2 | prices = [1,2,3,4,5] | 4 |
| 3 | prices = [7,6,4,3,1] | 0 |
From slow to fast
Add max(0, prices[i] − prices[i − 1]) for every i.
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;
}
}Verdict: The state machine collapses to this.
Before you submit
Test these inputs
Mistakes people make
Interview
Does this count as "one transaction per day"?