LeetCode_Array_123. Best Time to Buy and Sell Stock III买卖股票的最佳时机III（C++）

程序员文章站 2022-07-07 15:15:46

...

1，题目描述

英文描述

1，题目描述

英文描述

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 two transactions.

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

Example 1:

Input: [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
   Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.
Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
   Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
   engaging multiple transactions at the same time. You must sell before buying again.
Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

中文描述

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

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

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

示例 1:

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

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
   注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
   因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:

输入: [7,6,4,3,1]
输出: 0
解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2，解题思路

思路扩展

假设交易次数为k。

当k=1时，也就是这一题@&再见萤火虫&【LeetCode_Array_121. Best Time to Buy and Sell Stock买卖股票的最佳时机（C++）】。

通过设置一个变量minPrice记录出现过的最低价格，并在一次遍历过程中，更新minPrice以及ans = max(ans, prices[i] - minPrice)，即可得出结果；（相当于记录卖出之前的最低价格，在遍历过程比较每次卖出可能获得的收益，取最大值即可）

当k = 无数次时，即这一题@&再见萤火虫&【LeetCode_Array_122. Best Time to Buy and Sell Stock II买股票的最佳时机（C++）】。

解决这题时有点类似于贪心算法，同样是记录卖出前的最低价格minPrice，但是一旦遇到 prices[i] 卖出时，利润少于上一笔 prices[i-1] 的利润，就果断按照上一笔的价格卖出，ans累加利润 prices[i-1] - minPrice ，并更新minPrice，直至结束；

算法

参考@Clark【小白通俗易懂的解法】，简洁高效，上乘之作。

核心思想：第一次交易获得的利润，抵消第二次交易时买入的价格，使得整体来看算法仍与 k = 1 相同。

首先，第一次交易在第二次之前（虽然听上去有点傻，但此处是为了强调只有第一次交易结束，第二次交易才能开始，并且利用第一次交易的结果）；

使用minPrice1记录第一次交易时买入的最低价格，遍历数组的同时，更新第一次交易获得的利润 maxProfit1 = max(maxProfit, proces[i] - minPrice)；

用minPrice2记录第二次交易时买入的最低价格，但minPrice2 = prices[i] - maxProfit（第二次买入的价格为当前价格 - 第一次交易获得的最大利润），更新两次交易可以获得的最大利润maxProfit2 = prices[i] - minPrice2 ，（有种动态规划的感觉，巧妙利用了上一次的计算结果）；

3，AC代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minPrice1 = INT_MAX, minPrice2 = INT_MAX;
        int maxProfit1 = 0, maxProfit2 = 0;
        for(int i = 0; i < prices.size(); i++){
            minPrice1 = min(minPrice1, prices[i]);
            maxProfit1 = max(maxProfit1, prices[i] - minPrice1);    // 第一次交易获得的最大利润
            minPrice2 = min(minPrice2, prices[i] - maxProfit1);     // 买入价格 = 当前价格 - 上一次交易获得的利润
            maxProfit2 = max(maxProfit2, prices[i] - minPrice2);    // 更新两次交易获得的总的最大利润
        }
        return maxProfit2;
    }
};

4，解题过程

第一博

这里本想套用k = 无数次时的算法，只不过ans只累加两次最大利润，然而结果有问题。如下图所示，由于k=无数次时，采用的是贪心算法（一旦当前价格prices[i]低于上一笔价格prices[i-1]就立刻按照上一笔的价格卖出），所以图*有三次交易，所获利润分别为3、5、7，显然选择后两次交易，所以ans = 12；

然而可以看出第一次交易时的价格并不是利润最大化的时刻，使得所获利润最大，应该先以价格 1 买入，在价格 7 卖出，然后在价格 2 买入，在价格 9 卖出，因此所获最大收益为 6 + 7 = 13；

代码如下
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int dif;
        if(prices.size() == 0) return 0;
        int minPrice = prices[0], maxPrice = prices[0];
        vector<int> tem(2); // 保证tem[0] <= tem[1]
        for(int i = 0; i < prices.size(); ++i){
            if(prices[i] < maxPrice){
                dif = maxPrice - minPrice;
                maxPrice = minPrice = prices[i];
                if(dif > tem[1]) {
                    tem[0] = tem[1];
                    tem[1] = dif;
                }
                else if(dif > tem[0]) tem[0] = dif;
            }else{
                maxPrice = prices[i];
                minPrice = min(minPrice, prices[i]);
            }
        }
        dif = maxPrice - minPrice;
        if(dif > tem[1]) {
            tem[0] = tem[1];
            tem[1] = dif;
        }
        else if(dif > tem[0]) tem[0] = dif;
        return tem[0] + tem[1];

    }
};