Best Time to Buy and Sell Stock II
Multiple buy/sell transactions, capture every positive day-over-day delta.
2 min read
greedy array
Problem#
You may buy and sell as many times as you like (no holding two stocks at once). Maximize total profit.
Examples#
[7,1,5,3,6,4]→7(buy 1 sell 5, buy 3 sell 6)[1,2,3,4,5]→4
Constraints#
1 <= prices.length <= 3 * 10^4.
Approach#
Sum every positive day-over-day delta.
Solution#
class Solution {public: int maxProfit(vector<int>& prices) { int profit = 0; for (int i = 1; i < (int)prices.size(); ++i) { if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1]; } return profit; }};func maxProfit(prices []int) int { profit := 0 for i := 1; i < len(prices); i++ { if prices[i] > prices[i-1] { profit += prices[i] - prices[i-1] } } return profit}from typing import List
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 profitvar maxProfit = function(prices) { let profit = 0; for (let 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) { 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; }}function maxProfit(prices: number[]): number { let profit = 0; for (let i = 1; i < prices.length; i++) { if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1]; } return profit;}Editorial#
Any monotone-increasing run from lo to hi decomposes into adjacent deltas: hi - lo = sum of (prices[i] - prices[i-1]). Capturing every positive delta gives the same total as any clever buy-low/sell-high pairing. Negative deltas don’t contribute (we skip those).
Complexity#
- Time: O(n).
- Space: O(1).
Concept revision#
Related#