資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學帶冷卻期的股票買賣最佳時機 (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
廣告