带冷却期的股票买卖最佳时机 (C++)

假设我们有一个数组，其中第 i 个元素代表第 i 天某只股票的价格。我们需要设计一个算法来找到最大利润。我们可以进行任意多次交易（所以，可以多次买卖股票）。但是，我们必须遵守以下规则：

  • 我们不能同时进行多笔交易（所以，必须先卖出股票才能再次买入）。
  • 卖出股票后，第二天不能买入股票。（所以需要一天的冷却期）

如果输入是 [1,2,3,0,2]，则输出为 3，序列为 [买入, 卖出, 冷却, 买入, 卖出]

为了解决这个问题，我们将遵循以下步骤：

  • endWithSell := 0, endWithBuy := -∞, prevBuy := 0, prevSell := 0
  • for i := 0 to 给定数组的大小
    • prevBuy := endWithBuy
    • endWithBuy := max(endWithBuy, prevSell – Arr[i])
    • prevSell := endWithSell
    • endWithSell := max(endWithSell, prevBuy + Arr[i])
  • return endWithSell

让我们来看下面的实现，以便更好地理解：

示例

 在线演示

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int maxProfit(vector<int>& p) {
      int endWithSell = 0;
      int endWithBuy = INT_MIN;
      int prevBuy =0, prevSell = 0;
      for(int i =0;i<p.size();i++){
         prevBuy = endWithBuy;
         endWithBuy = max(endWithBuy,prevSell - p[i]);
         prevSell = endWithSell;
         endWithSell = max(endWithSell, prevBuy + p[i]);
      }
      return endWithSell;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,3,0,2};
   cout << (ob.maxProfit(v));
}

输入

[1,2,3,0,2]

输出

3

更新于：2020年5月4日

浏览量：116

开启您的职业生涯

完成课程获得认证

开始学习
广告