LeetCode 가 주식 을 매매 하기에 가장 좋 은 시기 | | |

5555 단어 LeetCode선형 DP
제목 링크
제목 설명
배열 을 지정 합 니 다. 그 i 번 째 요 소 는 주어진 주식 이 i 일 째 가격 입 니 다.당신 이 얻 을 수 있 는 최대 이윤 을 계산 하기 위해 알고리즘 을 설계 하 세 요.너 는 최대 두 건의 거래 를 완성 할 수 있다.주의: 당신 은 여러 가지 거래 에 동시에 참여 할 수 없습니다.수입: [3, 3, 5, 0, 0, 3, 1, 4] 수출: 6 설명: 4 일 (주식 가격 = 0) 에 매입 하고 6 일 (주식 가격 = 3) 에 판매 하면 이 거래 소 는 이윤 = 3 - 0 = 3 을 얻 을 수 있다.이 어 7 일 째 (주식 가격 = 1) 에 매 수 했 고 8 일 째 (주식 가격 = 4) 에 팔 았 으 며 이 거래 소 는 이익 = 4 - 1 = 3 을 얻 을 수 있 었 다.
문제 풀이 의 사고 방향.
이 문 제 는 정말 어렵다 고 생각한다.스스로 경 기 를 할 때 동태 계획 을 엉망 으로 배 워 서 정말 안 된다.지금 이 참 에 연습 이나 잘 해.구체 적 으로 코드 참조.
프로그램 코드
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
    if(n == 0){return 0;}
    int dp_i_1_0 = 0;
    int dp_i_1_1 = -prices[0];
    int dp_i_2_0 = 0;
    int dp_i_2_1 = -prices[0];
    for(register int i = 0;i < n;i++){
        dp_i_1_0 = max(dp_i_1_0,dp_i_1_1 + prices[i]);
        //                     ,
        //            
        dp_i_1_1 = max(dp_i_1_1,0 - prices[i]);
        //          
        //        
        dp_i_2_0 = max(dp_i_2_0,dp_i_2_1+prices[i]);
        //              
        dp_i_2_1 = max(dp_i_2_1,dp_i_1_0-prices[i]);
        //         
        //      
    }
    return dp_i_2_0;
    }
};

어떤 사내 가 이 시리즈 에 대해 매우 상세 하 게 말 했다.

좋은 웹페이지 즐겨찾기