베 스 트 주식 구 매 시기 냉동 기간 포함

11287 단어 LeetCode
질문 설명:
정수 배열 을 정 하 는데 그 중에서 i 번 째 요 소 는 i 일의 주식 가격 을 대표 합 니 다.
하나의 알고리즘 을 설계 하여 최대 이윤 을 계산 해 내다.다음 과 같은 제약 조건 을 만족 시 키 면 당신 은 가능 한 한 많은 거래 를 완성 할 수 있 습 니 다 (주식 을 여러 번 매매).
너 는 여러 건의 거래 에 동시에 참여 할 수 없다.
주식 을 팔 고 나 면 다음날 주식 을 살 수 없다.
예시:
입력: [1, 2, 3, 0, 2]
출력: 3
설명: 해당 거래 상 태 는: [매입, 매도, 냉동기, 매입, 매도]
입력 설명:
먼저 prices 배열 요소 수 n 을 입력 한 다음 n 개의 정 수 를 입력 하 십시오.
사고방식: 3 가지 상태 로 나 뉜 다: dp [i] [0], dp [i] [1], dp [i] [2] 상태 0: 주식 보유, 상태 1: 주식 매각, 상태 2: 냉동기 하루 의 주식 가격 은 모두 전날 과 관계 가 있 는 상태 간 의 전환: 상태 0: dp [i] [0] 은 dp [i - 1] [0] 을 바탕 으로 계속 주식 을 보유 할 수도 있 고 dp [i - 1] [2] 의 냉동기 이후 의 주식 구 매 dp [2] [0]=max(dp[i-1][0],dp[i-1][2]-price[i]);
상태 1: dp [i] [1] 는 dp [i - 1] [0] 에 기초 한 주식 매각 dp [i] [1] = dp [i - 1] [0] + price [i] 일 뿐 입 니 다.
상태 2: dp [i] [2] 는 dp [i - 1] [1] 을 바탕 으로 하 는 냉동기 또는 dp [i - 1] [2] 를 바탕 으로 주식 을 살 수 있 지만 가격 때문에 주식 dp [i] [2] = max (dp [i - 1] [1], dp [i - 1] [2] 를 사지 않 는 다.
마지막 날 주식 을 보유 하 는 것 은 의미 가 없 기 때문에 마지막 결 과 는 매각 또는 냉동기 상태의 수익 인 return max (dp [len - 1] [1], dp [len - 1] [2]) 로 되 돌아 가 야 한다.
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
class Solution {
     
public:
    int maxProfit(vector<int>& prices) {
     
        if (prices.empty())
            return 0;
        int len=prices.size();
        vector<vector<int> >dp(len,vector<int>(3));
        dp[0][0]=-prices[0];
        for (int i=1; i<len;i++) {
     
            dp[i][0] = max(dp[i - 1][0],dp[i - 1][2]-prices[i]);
            dp[i][1] = prices[i]+dp[i - 1][0];
            dp[i][2] = max(dp[i - 1][1],dp[i - 1][2]);
        }
        return max(dp[len - 1][2],dp[len - 1][1]);
    }
};
int main()
{
     
    int n;
    cin>>n;
    vector<int>price;
    for(int i=0;i<n;i++){
     
        int a;
        cin>>a;
        price.push_back(a);
    }
    int res=Solution().maxProfit(price);
    cout<<res<<endl;
    return 0;
}

좋은 웹페이지 즐겨찾기