LeetCode(123)Best Time to Buy and Sell Stock3

제목은 다음과 같습니다.
Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most two transactions. Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
분석은 다음과 같습니다.
이전의 생각은 틀렸다. 그리고 이곳의 사고방식을 참고해 보니 나는 매우 분명하게 썼다고 생각한다.복사하여 붙여넣기:
“
앞의 두 문제와 비교하면 거래 횟수를 제한하기 때문에 이 문제가 가장 어렵다.문제를 해결하는 방법은 최대 두 건의 거래만 완성할 수 있고 거래 사이에 중첩이 없다면 divide and conquer이다.i를 0에서 n-1로 설정하면 각 i를 대상으로 prices의 하위 서열 [0,..., i][i,..., n-1]에서 각각 얻은 최대 이윤(첫 번째 문제)을 보면 된다.이렇게 초보적으로 계산하면 시간 복잡도는 O(n2)이다.개선: 개선 방법은 동적 기획이다. 바로 첫 번째 스캔이다. 먼저 하위 서열 [0,...,i]의 최대 이윤을 계산하고 하나의 그룹으로 저장하면 시간은 O(n)이다.두 번째 단계는 역방향 스캐닝으로 하위 서열 [i,..., n-1]의 최대 이윤을 계산한다. 이 단계는 이전 단계의 결과와 결합하여 최종 최대 이윤을 계산할 수 있다. 이 단계도 O(n)이다.그래서 마지막 알고리즘의 복잡도는 O(n)이다.
”
내 코드

// 56ms    
class Solution {
public:
    int maxProfit(vector<int> &prices) {
        if(prices.size()<=1)
            return 0;
        int max_profit=0;
        int vec_size=(int)prices.size();
        int* left_sz=new int[vec_size];
        int* right_sz=new int[vec_size];
        left_sz[0]=0;
        right_sz[vec_size-1]=0;
        int max_left_profit=0;
        int max_right_profit=0;
        int small_buy=0;
        int large_sell=vec_size-1;
        
        for(int j=1;j<vec_size;j++){
            int i=j-1;
            if(prices[i]<prices[small_buy])
                small_buy=i;
            int tmp_profit=prices[j]-prices[small_buy];
            if(tmp_profit>max_left_profit)
                max_left_profit=tmp_profit;
            left_sz[j]=max_left_profit;
        }
        
        for(int j=vec_size-1;j>=1;j--){
            int i=j-1;
            if(prices[j]>prices[large_sell])
                large_sell=j;
            int tmp_profit=prices[large_sell]-prices[i];
            if(tmp_profit>max_right_profit)
                max_right_profit=tmp_profit;
            right_sz[i]=max_right_profit;
        }
        
        for(int k=0;k<vec_size;k++){
            if(left_sz[k]+right_sz[k]>max_profit)
                max_profit=left_sz[k]+right_sz[k];
         //   std::cout<<"k="<<k<<" ,left_sz[k]="<<left_sz[k]<<" ,right_sz[k]="<<right_sz[k]<<std::endl;
        }
        delete [] left_sz;
        delete [] right_sz;
        return max_profit;
    }
};

요약 증가:
1. 사실 내가 처음에 생각한 것은 욕심 전략이었다.한 시간대에 이윤을 극대화하는 거래를 한 번 하고 남은 시간대에 이윤을 극대화하는 거래를 한 번 하는 것이다.Best Time to Buy and Sell Stock1의 사고방식을 따라 계속 내려가면 쉽게 나올 수 있는 생각이었지만, 제출하고 보니 잘못된 생각이었다.'{6,1,3,2,4,7}'이라는 테스트 사례에서 통과할 수 없습니다.욕심 알고리즘을 사용하면 [1,7]+[1,1],sum=6을 찾을 수 있지만, 사실 진정한 최우선은 [1,3]+[2,7],sum-7이다.즉, 욕심이 난 1차 최대화 거래에 두 번으로 나눌 수 있는 거래가 딱 들어있고 이 두 번의 거래가 욕심이 낸 두 번의 거래보다 조금 작다면 둘을 합친 합은 욕심 전략이 찾은 합을 초과할 수 있다는 것이다.
2. 이 문제의 동태적인 기획은 매우 재미있다. 첫눈에 보통의bottom-up 형식이 아니라고 생각했다. 사실 곰곰이 생각해 보면 왼쪽은 한 번, 오른쪽은 한 번 계산하면 두번에bottom-up의 사상을 운용했다고 볼 수 있다.
3. stock 질문은 4개의 시리즈가 있는데 각각 1, 2, 3, 4.
참조 자료:
(1) UniEagle의 블로그