Trong bài toán này, chúng ta được cung cấp một mảng stkprice [] biểu thị giá của một số cổ phiếu nhất định vào ngày thứ i. Nhiệm vụ của chúng tôi là tạo một chương trình để tính toán lợi nhuận tối đa sau khi mua và bán cổ phiếu bằng C ++.
Mô tả sự cố - Ở đây, chúng ta cần kiểm tra thời điểm có thể mua và bán cổ phiếu để thu lợi. Để thu được lợi nhuận, chúng ta cần mua cổ phiếu với giá thấp và bán nó khi giá tăng. Và lặp lại tương tự khi gặp lại sự cố.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
stkprice[] = {120, 310, 405, 210, 150, 550} Đầu ra
685
Giải thích
Mua vào ngày 1 và bán vào ngày 3, sẽ thu được lợi nhuận là 285.
Sau đó, Mua vào ngày 5 và bán vào ngày 6, sẽ thu được lợi nhuận là 400.
Điều này làm cho tổng lợi nhuận là (400 + 285) =685
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản sẽ là kiểm tra tất cả các kết hợp có thể có của chu kỳ mua-bán. Hãy thử kết hợp chu kỳ mua-bán từ mỗi ngày đến mua lần đầu bán cuối cùng cho ngày hiện tại. Và thực hiện chu kỳ mang lại lợi nhuận tối đa.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra
The Maximum profit is 4196007
Một giải pháp hiệu quả hơn là dựa trên việc tìm kiếm lợi nhuận tối đa từ giao dịch bằng cách tìm kiếm lợi nhuận tối đa cho mỗi giao dịch. Điều này có thể được thực hiện bằng cách tìm ra cực tiểu và cực đại cục bộ cho các ngày giao dịch. Cực tiểu cục bộ là những ngày mà giá cổ phiếu thấp hơn cả ngày hôm trước và ngày hôm sau của nó. Andmaxima đối lập với minima. Nếu không có cực tiểu cục bộ (trong chỉ mục 0 đến n-2), thì ngày của họ không thể có lãi.
Để tối đa hóa lợi nhuận, chúng tôi sẽ mua cổ phần tại cực đại cục bộ và bán cổ phần tại cực đại cục bộ tiếp theo và thực hiện tương tự đối với cặp cực đại-cực đại địa phương. Cộng tất cả các khoản lợi nhuận tối đa tối đa, chúng tôi sẽ nhận được Lợi nhuận tối đa.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra
The maximized profit is 685