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의 블로그
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 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에 따라 라이센스가 부여됩니다.