188 Best Time to Buy and Sell Stock IV

Description

Say you have an array for which theithelement is the price of a given stock on dayi.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Discussion

Method 1

DP 划分 dp[k][i] = max profit gained with k transaction from 0 to time i.

Kadane's Algorithm.

class Solution {
    public int maxProfit(int k, int[] prices) {
        int profits[prices.length - 1];
        int rst; = 0
        for(int i = 0; i < profits.length; ++i) {
            profits[i] = prices[i + 1] - prices[i];
        }   

        if(k > prices.length / 2) {
            for(int i = 0; i < profits.length; ++i) {
                rst += (profits[i] > 0)? profits[i] : 0;
            }
        }
        else {
            int local[profits.length + 1][k + 1];
            int global[profits.length + 1][k + 1];

            for(int iProfit = 1; iProfit <= profits.length; ++iProfit) {
                for(int kl = 1; kl <= k && iProfit / 2 > kl; ++kl) {
                    local[iProfit][kl] = max(local[iProfit - 1][kl], global[iProfit - 1][kl - 1]) + profits[iProfit - 1];
                    global[iProfit][kl] = max(local[iProfit][kl], global[iProfit - 1][kl]);
                }
            }

            rst = global[prices.length][k];
        }

        return rst;
    }
}

Method 2 Leetcode

DP 划分 dp[k][i] = max profit gained with k transaction from 0 to time i.

    public int maxProfit(int k, int[] prices) {
        int len = prices.length;
        if (k >= len / 2) return quickSolve(prices);

        int[][] t = new int[k + 1][len];
        for (int i = 1; i <= k; i++) {
            int tmpMax =  -prices[0];
            for (int j = 1; j < len; j++) {
                t[i][j] = Math.max(t[i][j - 1], prices[j] + tmpMax);
                tmpMax =  Math.max(tmpMax, t[i - 1][j - 1] - prices[j]);
            }
        }
        return t[k][len - 1];
    }


    private int quickSolve(int[] prices) {
        int len = prices.length, profit = 0;
        for (int i = 1; i < len; i++)
            // as long as there is a price gap, we gain a profit.
            if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
        return profit;
    }