188. Best Time to Buy and Sell Stock IV

Given an array of integers representing a stock’s price on each day. On each day you can only make one operation: either buy or sell one unit of stock, and at any time you can only hold at most one unit of stock, and you can make at in total. Determine the maximum profit you can make.

Example: {2, 3, 2, 1, 4, 5, 2, 11}, K = 3, the maximum profit you can make is (3 - 2) + (5 - 1) + (11 - 2)= 14

Analysis

Code link: https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/StockBuySellKTransactions.java

Youtube link: https://www.youtube.com/watch?v=oDhu5uGq_ic&t=1s

This is slow method but easier to understand. Time complexity is O(k * number of days ^ 2)

T[i][j] = max(T[i][j-1], max(prices[j] - prices[m] + T[i-1][m])) where m is 0...j-1

i表示most i transactions; j is stock price on each day.

Solution

public int maxProfitSlowSolution(int prices[], int K) {
    if (K == 0 || prices.length == 0) {
        return 0;
    }
    int T[][] = new int[K + 1][prices.length];

    for (int i = 1; i < T.length; i++) {
        for (int j = 1; j < T[0].length; j++) {
            int maxVal = 0;
            for (int m = 0; m < j; m++) {
                maxVal = Math.max(maxVal, prices[j] - prices[m] + T[i - 1][m]);
            }
            T[i][j] = Math.max(T[i][j - 1], maxVal);
        }
    }
    return T[K][prices.length - 1];
}