Vault 101

xjay2007's Blog

0%

LeetCode 188. 买卖股票的最佳时机 IV

发表于 更新于 分类于 ， Valine：

题目描述

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

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

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

示例 1:

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

示例 2:

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

题解

解法一

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// C++
int maxProfit(int k, vector<int>& prices) {
    int size = (int)prices.size();
    if (k >= size/2 ) {
        // 交易超过数组一半，最多可完成size/2次交易
        int profit = 0;
        for (auto i = 1; i < size; ++i) {
            if (prices[i] > prices[i-1]) {
                profit += (prices[i] - prices[i-1]);
            }
        }
        return profit;
    }
    vector<int> buys(k+1, INT_MIN);
    vector<int> solds(k+1, 0);
    for (auto p : prices) {
        for (auto j = k; j > 0; --j) {
            solds[j] = max(solds[j], buys[j] + p);
            buys[j] = max(buys[j], solds[j-1] - p);
        }
    }
    return solds[k];
}

类似题目： 买卖股票的最佳时机 III
参考资料：https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/discuss/39611/Is-it-Best-Solution-with-O(n)-O(1).

相似文章