Thời điểm tốt nhất mua bán cổ phiếu với thời gian nghỉ trong C++

Giả sử chúng ta có một mảng mà phần tử thứ i là giá của một cổ phiếu cho trước vào ngày i. Chúng ta phải thiết kế một thuật toán để tìm lợi nhuận tối đa. Chúng ta có thể hoàn thành bao nhiêu giao dịch cũng được (mua một và bán một cổ phiếu nhiều lần). Nhưng chúng ta phải tuân theo các quy tắc sau:

• Chúng ta không thể tham gia nhiều giao dịch cùng một lúc (phải bán cổ phiếu trước khi mua lại).
• Sau khi bán cổ phiếu, chúng ta không thể mua cổ phiếu vào ngày tiếp theo (nghỉ 1 ngày).

Nếu đầu vào như [1,2,3,0,2], thì đầu ra sẽ là 3, chuỗi là [mua, bán, nghỉ, mua, bán].

Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau:

• endWithSell := 0, endWithBuy := -infinity, prevBuy := 0 và prevSell := 0
• for i := 0 đến kích thước mảng cho trước
  • prevBuy := endWithBuy
  • endWithBuy := max của endWithBuy và prevSell – Arr[i]
  • prevSell := endWithSell
  • endWithSell := max của endWithSell và prevBuy + Arr[i]
• trả về endWithSell

Hãy xem triển khai sau để hiểu rõ hơn:

Ví dụ

#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));
}

Đầu vào

[1,2,3,0,2]

Đầu ra

3