A different way to solve with logic in O(n*k), non DP code Java


  • 0
    T
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if (n < 2) {
            return 0;
        }
        int count = 0;
        int[] diff = new int[n-1];
        // for the case where k is large enough to get all the profit trades
        for (int i = 0; i < n-1; i++) {
            diff[i] = prices[i+1] - prices[i];
            if (diff[i] > 0) {
                count++;
            }
        }
        int res = 0;
        // able to get all profit
        if (count <= k) {
            for (int i = 0; i < n-1; i++) {
                res += Math.max(0, diff[i]);
            }
            return res;
        }
        // buy: -1, sell: 1, other: 0
        int[] actions = new int[n];
        int buy = 0, sell = 0;
        int updateBuy = 0, updateSell = 0;
        //  the logic here is: 
        //  when you have a result from k = 1 and begin k = 2, 
        //  you will see you will always end up keeping your action made for buy and sell actions in k = 1;
        //  consider: if you want to make two different trades and disregard the previous one,
        //            you will always end up replace one of the trade's buy with the buy date in k=1 and the sell date in k=1
        // when k is greater than 1, the same logic applies
        for (int i = 1; i <= k; i++) {
            int l = 0, r = 0;
            updateBuy = 0;
            updateSell = 0;
            boolean within = false;
            while (r < n) {
                if (!within) {// if you are out side the previous transaction period, look for max profit as normal 
                    buy = r;
                    sell = r;
                    while (r < n && actions[r] != -1) {
                        buy = prices[r] > prices[buy] ? buy : r;
                        if (prices[r] - prices[buy] > prices[updateSell] - prices[updateBuy]) {
                            updateSell = r;
                            updateBuy = buy;
                        }
                        r++;
                    }
                    within = !within;
                } else {// if you are within the previous transaction period, 
                        // you want to find a high price to sell first before you buy low to make a profit to meet the requirement
                    buy = r;
                    sell = r;
                    while (r < n && actions[r] != 1) {
                        sell = prices[r] < prices[sell] ? sell : r;
                        if (prices[sell] - prices[r] > prices[updateSell] - prices[updateBuy]) {
                            updateSell = sell;
                            updateBuy = r;
                        }
                        r++;
                    }
                    within = !within;
                }
                r++;
            }
            if (updateSell != 0 || updateBuy != 0) {
                actions[updateSell] = 1;
                actions[updateBuy] = -1;
            }
            res += prices[updateSell] - prices[updateBuy];
        }
        return res;
    }

Log in to reply
 

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