Leetcode - Best Time to Buy and Sell Stock

Question

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

This is a sliding_window question.

Idea

• Uses Kadane’s Algorithm (sliding window approach)
• We make the modification where our currSum is prices[R] - prices[L]

Kadane’s Modification How it works

• Keep track of a maxSum, and currSum
• Iterate throughout the array
• Check to make sure currSum is not negative, if it is, reset it to 0 + set l to r. The logic here is if this is true, right will always have the better price so we want to set l to r.
• Add the current number to currSum
• Set maxSum to the max(maxSum, currSum)
• Return maxSum

You can modify Kadane’s algorithm to use a sliding window approach which returns the indices of the sub-array instead of its sum…

How it works

• The same idea…
• Keep track of the maxSum, currSum, but now also maxL, and maxR which are your result L and R pointers
• Iterate through the array
• if currSum < 0, reset it to 0 and set L = R
• if currSum > maxSum, set maxSum = currSum, and set maxL and maxR

Solution