Skip to main content

81. Best Time to Buy and Sell Stock II

mediumAsked at Ola

Maximize profit from many buy/sell transactions of a stock.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

You are given an array prices where prices[i] is the price of a given stock on the ith day. On each day you may decide to buy and/or sell. You can hold at most one share at any time but may buy and sell on the same day. Return the maximum profit you can achieve.

Constraints

  • 1 <= prices.length <= 3 * 10^4
  • 0 <= prices[i] <= 10^4

Examples

Example 1

Input
prices = [7,1,5,3,6,4]
Output
7

Example 2

Input
prices = [1,2,3,4,5]
Output
4

Approaches

1. Recursive with state

Recurse with held/free state; intractable without memo.

Time
O(2^n)
Space
O(n)
// raw recursion of state machine

Tradeoff:

2. Greedy positive diffs

Sum every positive consecutive difference; that's the same as buying at every dip and selling at every peak.

Time
O(n)
Space
O(1)
function maxProfit(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;
}

Tradeoff:

Ola-specific tips

Ola checks if you spot the diff-sum trick; tie it to summing every positive surge differential across hour buckets.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

More Ola coding interview questions

See all Ola problems →

Companies that also ask Best Time to Buy and Sell Stock II