Problem of The Day: Best Time to Buy and Sell Stock II

5 min read 1159 words

Problem Statement

leetcode problem link

Solution [Accepted]

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        memo = {}
        def dp(i, holding):
            if i == len(prices):
                return 0
            if (i, holding) in memo:
                return memo[(i, holding)]

            dothing = dp(i + 1, holding)
            sell = buy = 0
            if holding:
                sell = dp(i + 1, False) + prices[i]
            else:
                buy = dp(i + 1, True) - prices[i]

            memo[(i, holding)] = max(dothing, buy, sell)
            return memo[(i, holding)]

        return dp(0, False)

public class Solution {
    public Dictionary<(int, int), int> Memo = new Dictionary<(int, int), int>();

    public int Helper(int i, int isHolding, int[] prices) {
        if (i == prices.Length)
            return 0;
        if (Memo.ContainsKey((i, isHolding)))
            return Memo[(i, isHolding)];
        int dothing = 0, buy = 0, sell = 0;
        dothing = Helper(i + 1, isHolding, prices);
        if (isHolding == 1) {
            sell = Helper(i + 1, 0, prices) + prices[i];
        } else {
            buy = Helper(i + 1, 1, prices) - prices[i];
        }

        Memo[(i, isHolding)] = Math.Max(dothing, Math.Max(buy, sell));
        return Memo[(i, isHolding)];
    }

    public int MaxProfit(int[] prices) {
        return Helper(0, 0, prices);
    }
}

time: O(n) space: O(n)

Editorial

Approach 1: Brute Force [TLE]

public class Solution {
    public int MaxProfit(int[] prices) {
        return Calculate(prices, 0);
    }

    private int Calculate(int[] prices, int s) {
        if (s >= prices.Length)
            return 0;
        int max = 0;
        for (int start = s; start < prices.Length; start++) {
            int maxprofit = 0;
            for (int i = start + 1; i < prices.Length; i++) {
                if (prices[start] < prices[i]) {
                    int profit =
                        Calculate(prices, i + 1) + prices[i] - prices[start];
                    if (profit > maxprofit)
                        maxprofit = profit;
                }
            }

            if (maxprofit > max)
                max = maxprofit;
        }

        return max;
    }
}

Approach 2: Peak Valley Approach

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        i = 0
        valley = prices[0]
        peak = prices[0]
        maxprofit = 0
        while i < len(prices) - 1:
            while i < len(prices) - 1 and prices[i] >= prices[i + 1]:
                i += 1
            valley = prices[i]
            while i < len(prices) - 1 and prices[i] <= prices[i + 1]:
                i += 1
            peak = prices[i]
            maxprofit += peak - valley
        return maxprofit

public class Solution {
    public int MaxProfit(int[] prices) {
        int i = 0;
        int valley = prices[0];
        int peak = prices[0];
        int maxprofit = 0;
        while (i < prices.Length - 1) {
            while (i < prices.Length - 1 && prices[i] >= prices[i + 1]) i++;
            valley = prices[i];
            while (i < prices.Length - 1 && prices[i] <= prices[i + 1]) i++;
            peak = prices[i];
            maxprofit += peak - valley;
        }

        return maxprofit;
    }
}

time: O(n) space: O(1)