SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

Description

Given a list of stock prices for several days, where each price is associated with a day, you need to determine the maximum profit you can achieve by buying and selling the stock. You are allowed to complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) but you must pay a transaction fee for each trade. The goal is to maximize your profit after considering the transaction fees.

Intuition

The problem can be broken down into a series of decisions: whether to buy a stock, sell a stock, or do nothing on a given day. The challenge lies in balancing these decisions with the transaction fees. The key observation is that at any point, you either hold a stock or you don’t, and this state should guide your actions.

Approach

1. State Definition:

   • Use two states to keep track of your profit:
     • dp[0] for the maximum profit when you do not hold any stock.
     • dp[1] for the maximum profit when you do hold a stock.

2. State Transition:

   • When not holding a stock (dp[0]):
     • Either you stay in this state by doing nothing.
     • Or you sell the stock you were holding and add the profit from the sale to your current profit.
   • When holding a stock (dp[1]):
     • Either you stay in this state by doing nothing.
     • Or you buy a stock today, subtracting the stock price and the fee from your current profit.

3. Iterate over each day to update these states based on the stock prices and the transitions defined.

4. The answer will be in dp[0] after processing all days because you end up with maximum profit by not holding any stock at the end.

Complexity

Time Complexity:

O(n), where n is the number of days (or the length of the price array). We iterate through the price list once.

Space Complexity:

O(1), as we are using only a few variables to maintain the states and do not require any additional space proportional to the input size.

Code

C++

class Solution {
public:
    int maxProfit(std::vector<int>& prices, int fee) {
        int n = prices.size();
        std::vector<int> dp(2, 0);
        dp[0] = 0;                // Max profit if not holding a stock
        dp[1] = -prices[0] - fee; // Max profit if holding a stock

        for (int i = 1; i < n; ++i) {
            dp[0] = std::max(dp[0], dp[1] + prices[i]);          // Max of not holding today or selling today
            dp[1] = std::max(dp[1], dp[0] - prices[i] - fee);    // Max of holding today or buying today
        }

        return dp[0]; // Return max profit when not holding any stock
    }
};

Python

class Solution:
    def maxProfit(self, a: list[int], f: int) -> int:
        m = {}
        return self.pp(a, 0, 1, f, m)

    def pp(self, a, i, buy, f, m):
        if i >= len(a):
            return 0
        if i not in m:
            m[i] = {}
        if buy in m[i]:
            return m[i][buy]

        if buy:
            k = max(self.pp(a, i + 1, 0, f, m) - a[i] - f, self.pp(a, i + 1, 1, f, m))
        else:
            k = max(a[i] + self.pp(a, i + 1, 1, f, m), self.pp(a, i + 1, 0, f, m))

        m[i][buy] = k
        return k

Java

class Solution {
    public int maxProfit(int[] a, int f) {
        Map<Integer, Map<Integer, Integer>> m = new HashMap<>();
        return pp(a, 0, 1, f, m);
    }

    private int pp(int[] a, int i, int buy, int f, Map<Integer, Map<Integer, Integer>> m) {
        if (i >= a.length) return 0;
        if (!m.containsKey(i)) m.put(i, new HashMap<>());
        Map<Integer, Integer> h = m.get(i);
        if (h.containsKey(buy)) {
            return h.get(buy);
        }

        int k = 0;
        if (buy == 1) {
            k = Math.max(pp(a, i + 1, 0, f, m) - a[i] - f, pp(a, i + 1, 1, f, m));
        } else {
            k = Math.max(a[i] + pp(a, i + 1, 1, f, m), pp(a, i + 1, 0, f, m));
        }

        h.put(buy, k);
        return k;
    }
}

JavaScript

var pp = (a,i,buy,f,m) => {
    if(i>=a.length) return 0;
    let h = m.has(i) ? m.get(i) : new Map();
    if(h.has(buy)) {
        return h.get(buy);
    }

    let k =0;
    if(buy) {
        k = Math.max(pp(a,i+1,0,f,m)-a[i]-f,  pp(a,i+1,1,f,m));
    } else {
        k= Math.max(a[i]+pp(a,i+1,1,f,m), pp(a,i+1,0,f,m));
    }

    h.set(buy,k);
    m.set(i,h);
    return k;
}
var maxProfit = function (a, f) {
    let m = new Map();
    return pp(a,0,1,f,m);
};