Algorithm to get max profit from stock transactions [LC150]

Hello friends,

Today let’s go over the algorithm to find maximum profit out of stock buy and sell. Let’s first understand the problem statement.

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. If you cannot achieve any profit, return 0. Now there are typically two cases.

Case-1: You can do transaction only one time. a day to buy one stock and choose a different day in the future to sell that stock. (https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description)

Case-2: You can buy and sell any number of times however can only hold at most one share of the stock at any time.

(https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/)

Now let’s go over case-1 in detail.

Case 1: Max Profit out of one transaction

Example 1:

Input: prices = [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. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1], Output: 0

Explanation: In this case, no transactions are done and the max profit = 0.

Constraint:

1 <= prices.length <= 10^5 and 0 <= prices[i] <= 10^4

Solution:

Approach-1 (Brute): 2 cascade loops, Time complexity : O(n^2)

private static void MaxProfit()
{
int[] prices = { 7, 1, 5, 3, 6, 4 };

int max = 0;
int diff = 0;
for (int i = 0; i < prices.Length; i++) {
for (int j = i+1; j<prices.Length; j++) {
diff = prices[j] - prices[i];
if (diff > max) {
max = diff;
}
}
}
Console.Write(max);
}

Approach-2 (Better): 1 loop, Time complexity : O(n)

private static void MaxProfit2()
        {
            int[] prices = { 7, 1, 5, 3, 6, 4 };

            int maxPrice = 0;
            int diff;
            int min = prices[0];

            for (int i = 1; i < prices.Length; i++) {
                diff = prices[i] - min;
                maxPrice = Math.Max(maxPrice, diff);
                min = Math.Min(min, prices[i]);
            }           
            Console.Write(maxPrice);
        } 

You can learn more at explainer video at https://youtu.be/V7dT5GIt_PM

Case 2: Max Profit out of any number of transactions

Example 1:

Input: prices = [7,1,5,3,6,4], Output: 7

Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4. Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3. Total profit is 4 + 3 = 7

Example 2:

Input: prices = [7,6,4,3,1], Output: 0

Explanation: In this case, no transactions are done and the max profit = 0.

Constraint: 1 <= prices.length <= 3* 10^4 and 0 <= prices[i] <= 10^4

Solution:

Approach-1 (Brute): Recursion with overlapping sub-problems, Time complexity : O(2^n), Space complexity: 0(n)

private static void MaxProfit()
{
    int[] prices = { 7, 1, 5, 3, 6, 4 };
    Console.Write(getMaxProfit(0, 1, prices, prices.Length));
}

private static int getMaxProfit(int index, int canBuy, int[] prices, int length)
{
    if (index == length) return 0;

    int maxProfit;
    
    if (canBuy == 1)
    {
        maxProfit = Math.Max(-prices[index] + getMaxProfit(index + 1, 0, prices, length),
                             getMaxProfit(index + 1, 1, prices, length));
    }
    else
    {
        maxProfit = Math.Max(prices[index] + getMaxProfit(index + 1, 1, prices, length),
                             getMaxProfit(index + 1, 0, prices, length));
    }

    return maxProfit;
}

Approach-2 (Better): Recursion with memorization, Time complexity : O(2*n) ~ O(n), Space complexity: O(n)

private static void MaxProfit()
        {
            int[] prices = { 7, 1, 5, 3, 6, 4 };
            List<List<int>> list = new List<List<int>>(prices.Length + 1);
            for (int i = 0; i < prices.Length; i++)
            {
                list.Add(new List<int> { -1, -1 });
            }
            Console.Write(getMaxProfit2(0, 1, prices, prices.Length, list));            
        }

        private static int getMaxProfit2(int idx, int buy, int[] prices, int n, List<List<int>> list)
        {
            if (idx == n) return 0;
            if (list[idx][buy] != -1) return list[idx][buy];

            int maxProfit;
            if (buy == 1)
            {
                maxProfit = Math.Max(-prices[idx] + getMaxProfit2(idx + 1, 0, prices, n, list),
                                        0 + getMaxProfit2(idx + 1, 1, prices, n, list));
            }
            else
            {
                maxProfit = Math.Max(prices[idx] + getMaxProfit2(idx + 1, 1, prices, n, list),
                                        0 + getMaxProfit2(idx + 1, 0, prices, n, list));
            }
            return list[idx][buy] = maxProfit;
        }

Approach-3 (Efficient): Tabulation Time complexity : O(n), Space complexity: O(1)

private static void MaxProfit()
        {
            int[] prices = { 7, 1, 5, 3, 6, 4 };
            int n = prices.Length;
            int currNotBuy, nextNotBuy = 0;
            int currBuy, nextBuy = 0;

            for (int idx = n - 1; idx >= 0; idx--)
            {
                currNotBuy = Math.Max(prices[idx] + nextBuy, 0 + nextNotBuy);
                currBuy = Math.Max(-prices[idx] + nextNotBuy, 0 + nextBuy);

                nextBuy = currBuy;
                nextNotBuy = currNotBuy;
            }
            Console.Write(nextBuy);            
        }

You can learn more at explainer video at- https://youtu.be/YmEbSyvlVfY

Hope you liked the article. Please share your comment/ suggestion.