🙏

জয়  শ্রী  রাম

🕉

---

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 = 6-1 = 5. Not 7-1 = 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 Sub-array 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 sub-array sum of profitRelativeToDayBefore[] gives the maximum achievable profit.

Java Code:

Login to Access Content

Python Code:

Login to Access Content

Instructor: