資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中買賣股票後的最大利潤
在這個問題中，我們得到一個數組 `stkprice[]`，它表示某隻股票在第 i 天的價格。我們的任務是建立一個程式來計算C++中買賣股票後的最大利潤。
問題描述 − 在這裡，我們需要檢查何時可以買賣股票以獲得利潤。為了獲得利潤，我們需要以低價買入股票，並在價格上漲時賣出。當價格再次下跌時，重複相同的操作。
讓我們來看一個例子來理解這個問題：
輸入
stkprice[] = {120, 310, 405, 210, 150, 550}輸出
685
解釋
第一天買入，第三天賣出，將獲得285的利潤。
之後，第五天買入，第六天賣出，將獲得400的利潤。
這使得總利潤為(400 + 285) = 685
解決方案方法
一個簡單的解決方案是檢查所有可能的買賣週期組合。嘗試從每一天開始的買賣週期組合到當前的第一天買入最後一天賣出。並選擇產生最大利潤的週期。
程式說明了我們解決方案的工作原理：
示例
#include <iostream>
using namespace std;
int max(int a, int b){
if(a > b)
return a;
return b;
}
int MaximizeProfit(int stkPrice[], int firstDay, int lastDay){
if (lastDay <= firstDay)
return 0;
int maxProfit = 0;
for (int i = firstDay; i < lastDay; i++) {
for (int j = i + 1; j <= lastDay; j++) {
if (stkPrice[j] > stkPrice[i]) {
int profit = ( stkPrice[j] - stkPrice[i] ) + MaximizeProfit(stkPrice, firstDay, i - 1) + MaximizeProfit(stkPrice, j + 1, lastDay);
maxProfit = max(maxProfit, profit);
}
}
}
return maxProfit;
}
int main(){
int stkPrice[] = { 120, 310, 405, 210, 150, 550 };
int days = 6 ;
cout<<"The Maximum profit is "<<MaximizeProfit(stkPrice, 0, days);
return 0;
}輸出
The Maximum profit is 4196007
一個更有效的解決方案是透過為每次交易尋找最大利潤來找到它們的總最大利潤。這可以透過找到交易日的區域性最小值和最大值來完成。區域性最小值是指股票價格低於其前一天和後一天的日子。最大值與最小值相反。如果沒有區域性最小值（在索引 0 到 n-2 之間），則這些天不會有利潤。
為了最大化利潤，我們將在區域性最小值買入股票，在下一個區域性最大值賣出，對最小值-最大值對重複此操作。將所有最小值-最大值利潤相加，我們將得到 maxProfit。
程式說明了我們解決方案的工作原理：
示例
#include <iostream>
using namespace std;
void MaximizeProfit(int price[], int n){
if (n == 1)
return;
int maxProfit = 0;
int i = 0;
while (i <= n - 1) {
while ((i <= n - 2) && (price[i + 1] <= price[i]))
i++;
int minima = i++;
while ((i < n) && (price[i] >= price[i - 1]))
i++;
int maxima = i - 1;
maxProfit += (price[maxima] - price[minima] );
// For displaying profit for one minima-maxima cycle
//cout <<"Stock bought on day "<<(minima+ 1 )<<" and Sold
on day "<<(maxima+1) <<" at a profit of "<<(price[maxima] - price[minima] )<<"\n";
}
cout<<"The maximized profit is "<<maxProfit;
}
int main(){
int stkPrice[] = { 120, 310, 405, 210, 150, 550 };
int days = 6;
MaximizeProfit(stkPrice, days);
return 0;
}輸出
The maximized profit is 685
更新於：2020年9月15日
695 次瀏覽
廣告