O(k) space simple and easy to understand java solution


  • 1
    F

    The key function is:

    • sell[i]=max(sell[i],buy[i]+price)
    • buy[i]=max(buy[i],sell[i-1]-price)

    The first function means that we are now at price, and we are in the ith transaction, and we are gonna ending with a sell, we can either do nothing which refers to sell[i], or we can sell the stock which means we must do buy[i] first and thus refers to buy[i]+price.
    The second function works in the similar way, we can either do nothing which refers to buy[i] or we can sell the stock in transaction i-1 first and buy the stock now, which refers to sell[i-1]-price, apparently, we need the max value of the two.
    The initial value of buy and sell can be thought as follows:
    we init buy to Integer.MIN_VALUE to confirm that it will be updated in the loop because of the Math.max function
    we init sell to 0 because we actually has nothing to sell and at first we got 0 money, the result will be our pure profit
    the return value is sell[k] which means we end with the sell of the kth transaction

    public int maxProfit(int k, int[] prices) {
            int n = prices.length;
            if (k >= n / 2) {
                int max = 0;
                for (int i = 1; i < n; i++)
                    max += Math.max(0, prices[i] - prices[i - 1]);
                return max;
            }
            int[] buy = new int[k + 1];
            int[] sell = new int[k + 1];
            Arrays.fill(buy, Integer.MIN_VALUE);
            Arrays.fill(sell, 0);
            for (int price : prices) {
                for (int i = k; i > 0; i--) {
                    sell[i] = Math.max(sell[i], buy[i] + price);
                    buy[i] = Math.max(buy[i], sell[i - 1] - price);
                }
            }
            return sell[k];
        }
    

  • 0
    S

    nice solution! easy to follow! Had one question, how did you figure out prove to yourself that if k >= n/2 then the max profit was simply the sum of all possible profits?


  • 1
    F

    @smarin a transaction consists of two events: buy and sell, so n events consisits of at most n/2 transactions.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.