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

Algorithms and Data Structures: TheAlgorist.com

System Design: SystemsDesign.Cloud

Low Level Design: LowLevelDesign.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:
This is a Premium content.
Please subscribe to Algorithms course to access the code.
Python Code:
This is a Premium content.
Please subscribe to Algorithms course to access the code.
Instructor:
Abhishek Dey
A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More
Microsoft  University of Florida
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn