Thời điểm tốt nhất để mua và bán cổ phiếu có thời gian hồi chiêu 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 nhất định vào ngày thứ i. Chúng tôi phải thiết kế một thuật toán để tìm ra lợi nhuận tối đa. Chúng tôi có thể hoàn thành bao nhiêu giao dịch tùy thích (Vì vậy, mua một và bán một cổ phiếu của cổ phiếu nhiều lần). Nhưng chúng ta phải tuân theo các quy tắc này -

• Chúng tôi không được tham gia nhiều giao dịch cùng một lúc (Vì vậy, chúng tôi phải bán cổ phiếu trước khi bạn mua lại).
• Sau khi chúng tôi bán cổ phiếu của mình, chúng tôi không thể mua cổ phiếu vào ngày hôm sau. (Vì vậy, hãy hạ nhiệt 1 ngày)

Nếu đầu vào là [1,2,3,0,2], thì đầu ra sẽ là 3, trình tự giống như [mua, bán, hồi chiêu, mua, bán]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• endWithSell:=0, endWithBuy:=-ve infinity, prevBuy:=0 và prevSell:=0
• for i:=0 to size of array đã cho
  • beforeBuy:=endWithBuy
  • endWithBuy:=max of endWithBuy và prevSell - Arr [i]
  • prevSell:=endWithSell
  • endWithSell:=max of endWithSell và prevBuy + Arr [i]
• return endWithSell

Hãy cùng chúng tôi xem cách 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