• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.
  • If you are a student, email to admin@thealgorists.com to get special student discount.



Problem Statement:


Say you have an array for which the ith 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:




This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.




Python Code:




This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.




The above content is written by:

Abhishek Dey

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

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave