Best Time to Buy and Sell Stock
Application of Kadane's Algorithm and Maximum Sum Subarray

Algorithms and Data Structures: TheAlgorist.com

System Design: www.System.Design

Low Level Design: LowLevelDesign.io

Frontend Engineering: FrontendEngineering.io
জয় শ্রী রাম
🕉
Problem Statement:
Say you have an array for which the i^{th} element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
Example 1:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 61 = 5. Not 71 = 6, as selling price needs to be larger than buying price.
Example 2:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
Solution:
This problem is an amazing use case of Kadane's Algorithm / Maximum Subarray Sum.
The solution discussed here is using the following observation:

Purchase a stock on any day i and sell that stock on any day j where i < j.
Total profit = sum of profit for each day relative to day before.
Say prices[] = {1, 5, 3, 10} and you buy on first day and sell on last day.
Total profit = (5  1) + (3  5) + (10  3) = 4 + (2) + 7 = 9
We create an array profitRelativeToDayBefore[] that stores profit for each day relative to day before.
profitRelativeToDayBefore[i] = prices[i]  prices[i  1]
, where prices[i] = stock price on day i.
Maximum subarray sum of profitRelativeToDayBefore[] gives the maximum achievable profit.
Java Code:
Login to Access Content
Python Code:
Login to Access Content