leetcode解题: Best time to buy and sell stock IV (188)

发表于 | 分类于

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.

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

解法:

比较难想清楚的一题。
需要用到两个dp matrix, 一个叫local, 一个叫global
local[i][j] 表示的是前i天做j次操作，最后一次sell正好是i天时的最大利润
global[i][j]表示的是前i天做j次操作，最大的利润
那么答案就是global[N][k]
local的递推关系是：
local[i][j]可以是i-1天已经完成了j次交易，那么只要把最后一天的交易顺延，就得到了i天完成j次交易。另外一个可能是到i - 1天完成了j - 1次交易，那么只要再加上新加的一天的交易即可。
global的递推关系是：
global[i][j]是要么新一天的local maxi, 或者是前一天的global max

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class Solution {
    public int maxProfit(int k, int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int n = prices.length;
        if (k > n) {
            return maxProfit_naive(prices);
        }
        int[][] global = new int[n][k + 1];
        int[][] local = new int[n][k + 1];
        for (int i = 1; i < n; i++) {
            int diff = prices[i] - prices[i - 1];
            for (int j = 1; j <= k; j++) {
                local[i][j] = Math.max(global[i - 1][j - 1] + diff, local[i - 1][j] + diff);
                global[i][j] = Math.max(local[i][j], global[i -1][j]);
            }
        }
        return global[n - 1][k];
    }
    private int maxProfit_naive(int[] prices) {
        int sum = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                sum += prices[i] - prices[i - 1];
            }
        }
        return sum;
    }
}