베 스 트 주식 구 매 시기 냉동 기간 포함
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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.