【每日算法Day 68】买卖股票的最佳时机 IV

LeetCode 188. 买卖股票的最佳时机 IV (opens new window)

题目描述

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例

输入: [3,2,6,5,0,3], k = 2
输出: 7
解释: 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

解题思路

在前面一题的基础上，对于每一天我们都假设从开始到这一天总共发生了k次交易（当k大于已经有的天数的1/2时，多余的部分其实就相当于同一天反复买入卖出，对结果没有影响）。对于一天内的第i次交易，我们使用当天价格减去上一次交易的最大利润来寻找这次交易要选择的最小值，再用当天价格减去最小值来寻找这次交易的最大收益。分别使用maxProfit[K]和min[K]来动态地更新在当前天如果已经总共交易了k次能获得的最大利润，以及完成k次交易后已知的最低的第k+1次交易买入价。

另外，k>n/2时就等于

public int maxProfit(int k,int[] prices) {
    if (k <= 0 || prices == null || prices.length <= 1) return 0;
    int n = prices.length;
    if (k > n/2) return maxProfit(prices);
    int[] min = new int[k];
    int[] maxProfit = new int[k];
    Arrays.fill(min, Integer.MAX_VALUE);
    for (int price : prices) {
        for (int i = 0; i < k; i++) {
            min[i] = Math.min(min[i], i == 0 ? price : price - maxProfit[i - 1]);
            maxProfit[i] = Math.max(maxProfit[i], price - min[i]);
        }
    }
    return maxProfit[k-1];
}

private int maxProfit(int[] prices) {
    int totalProfit = 0;
    for (int i = 1; i < prices.length; i++) {
        int greedyProfit = prices[i] - prices[i - 1];
        if (greedyProfit > 0) totalProfit += greedyProfit;
    }
    return totalProfit;
}