Best Time to Buy and Sell Stock IV

Say you have an array for which the ith element is the price of a given stock on day i.

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

Analysis

See reference

Code

public class Solution {
    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++){//for i==0,0笔transaction，一定为0，所以从i=1开始计算
            int tmpMax = - prices[0];
            for (int j=1; j<len; j++){//for j==0, t[i][j]=0,只有一天，所以从j=1开始计算
                t[i][j] = Math.max(t[i][j - 1], prices[j] + tmpMax);//取两种情况最大值：1.不考虑多一天的情况 2.考虑今天的，但是之前要少做一笔
                //tmpMax: the maximum profit of just doing at most i-1 transactions
                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;
    }
}

Reference

Leetcode