C++에서 쿨다운으로 주식을 사고 팔기 가장 좋은 시기

<시간/>

i번째 요소가 i일의 주어진 주식 가격인 배열이 있다고 가정합니다. 우리는 최대 이익을 찾는 알고리즘을 설계해야 합니다. 우리는 우리가 원하는 만큼 거래를 완료할 수 있습니다(따라서, 하나를 사고 주식의 한 주식을 여러 번 판매). 그러나 우리는 다음 규칙을 따라야 합니다 -

동시에 여러 거래에 참여할 수 없습니다(따라서 다시 구매하기 전에 해당 주식을 팔아야 함).
주식을 매도하고 나면 다음날 주식을 살 수 없습니다. (그래서 1일 진정)

입력이 [1,2,3,0,2]와 같으면 출력은 3이 되고 시퀀스는 [구매, 판매, 재사용 대기시간, 구매, 판매]

와 같습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

endWithSell :=0, endWithBuy :=-ve 무한대, prevBuy :=0 및 prevSell :=0
for i :=0에서 주어진 배열의 크기까지
- prevBuy :=endWithBuy
- endWithBuy :=endWithBuy 및 prevSell의 최대값 – Arr[i]
- prevSell :=endWithSell
- endWithSell :=endWithSell 및 prevBuy + Arr[i]의 최대값
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]