C++LeetCode(123.주식 을 사 는 가장 좋 은 시간의 3)실현

[LeetCode]123.Best Time to Buy and Sell Stock III 주식 사기 가장 좋 은 시간 3
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 (i.e., you must sell the stock before you buy again).
Example 1:
Input: [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.
Example 2:
Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
engaging multiple transactions at the same time. You must sell before buying again.
Example 3:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
이것 은 주식 을 사 는 가장 좋 은 시간 시리즈 문제 중 가장 어렵 고 복잡 한 것 이다.앞의 두 가지 이다.  Best Time to Buy and Sell Stock  화해시키다  Best Time to Buy and Sell Stock II  의 사고방식 은 모두 매우 간결 하고 명료 하 며 알고리즘 도 매우 간단 하 다.이것 은 최대 두 번 의 거래 를 요구 하고 최대 이윤 을 찾 아야 하 는 지,아니면 동적 계획 인 Dynamic Programming 으로 풀 어야 하 는 지,여기 서 우 리 는 두 개의 전달 공식 으로 각각 두 개의 변수 local 과 global 을 업데이트 해 야 한다.우 리 는 사실 적어도 k 번 의 거래 의 최대 이윤 을 구 할 수 있 고 통 해 를 찾 은 후에 k=2,즉 본 문제 의 해답 을 설정 할 수 있다.우 리 는 local[i][j]를 i 일 에 도착 할 때 최대 j 차 거래 를 할 수 있 고 마지막 거래 가 마지막 날 에 판매 하 는 최대 이윤 으로 정의 합 니 다.이것 은 부분 적 으로 가장 좋 습 니 다.그 다음 에 우 리 는 global[i][j]를 i 일 에 도착 할 때 최대 j 차 거래 를 할 수 있 는 최대 이윤 으로 정의 합 니 다.이것 은 전체 국면 에서 가장 좋 습 니 다.그들의 전달 식 은 다음 과 같다.
local[i][j] = max(global[i - 1][j - 1] + max(diff, 0), local[i - 1][j] + diff)
global[i][j] = max(local[i][j], global[i - 1][j])
그 중에서 국부 최 우수 치 는 전날 에 비교 하고 거래 를 한 번 적 게 하 는 전체 국면 에서 최 우수 와 0 이상 의 차 이 를 더 하 는 것 이다.전날 의 국부 최 우수 와 차이 점 에서 비교적 큰 수 치 를 취 하 는 것 이다.한편,전체 국면 에서 국부 최 우수 와 전날 의 전체 국면 이 가장 좋 고 코드 는 다음 과 같다.
해법 1:

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        if (prices.empty()) return 0;
        int n = prices.size(), g[n][3] = {0}, l[n][3] = {0};
        for (int i = 1; i < prices.size(); ++i) {
            int diff = prices[i] - prices[i - 1];
            for (int j = 1; j <= 2; ++j) {
                l[i][j] = max(g[i - 1][j - 1] + max(diff, 0), l[i - 1][j] + diff);
                g[i][j] = max(l[i][j], g[i - 1][j]);
            }
        }
        return g[n - 1][2];
    }
};

다음 과 같은 해법 은 2 차원 배열 을 1 차원 배열 로 대체 하면 공간 을 크게 절약 할 수 있 습 니 다.덮어 쓰 는 순서 관계 로 인해 우 리 는 j 가 2 에서 1 까지 필요 합 니 다.그러면 이미 덮어 쓴 값 이 아니 라 정확 한 g[j-1]값 을 얻 을 수 있 습 니 다.코드 는 다음 과 같 습 니 다.
해법 2:

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        if (prices.empty()) return 0;
        int g[3] = {0};
        int l[3] = {0};
        for (int i = 0; i < prices.size() - 1; ++i) {
            int diff = prices[i + 1] - prices[i];
            for (int j = 2; j >= 1; --j) {
                l[j] = max(g[j - 1] + max(diff, 0), l[j] + diff);
                g[j] = max(l[j], g[j]);
            }
        }
        return g[2];
    }
};

prices 배열 이 1,3,2,9 라 고 가정 하면 업데이트 할 때마다 local 과 global 의 값 을 살 펴 보 겠 습 니 다.
첫날 두 번 의 거래:첫날 한 번 의 거래:
local:　　  0 0 0 　　　　　　local:　　  0 0 0 
global:　　0 0 0　　　　　 　global:　　0 0 0
다음날 두 번 의 거래:다음날 한 번 의 거래:
local:　　  0 0 2 　　　　　　local:　　  0 2 2 
global:　　0 0 2　　　　　 　global:　　0 2 2
셋째 날 두 번 째 거래:셋째 날 한 번 의 거래:
local:　　  0 2 2 　　　　　　local:　　  0 1 2 
global:　　0 2 2　　　　 　　global:　　0 2 2
넷 째 날 두 번 째 거래:넷 째 날 한 번 의 거래:
local:　　  0 1 9 　　　　　　local:　　  0 8 9 
global:　　0 2 9　　　　　 　global:　　0 8 9
사실 상기 전달 공식 은 local[i][j]에 관 한 것 을 약간 줄 일 수 있 습 니 다.우리 가 정 의 했 던 local[i][j]는 i 일 에 최대 j 번 째 거래 를 할 수 있 고 마지막 거래 가 마지막 날 에 팔 리 는 최대 이윤 입 니 다.그리고 i 일 에 j 번 째 주식 을 팔면 다음 과 같 습 니 다.
1.오늘 방금 산 것
그러면 로 컬(i,j)=글로벌(i-1,j-1)
아무 일 도 하지 않 은 셈 이다
2.어제 산 것
그러면 Local(i,j)=Global(i-1,j-1)+diff
글로벌(i-1,j-1)에서 의 거래 에 오늘 한 표 까지.
3.더 일찍 산 것
그러면 Local(i,j)=Local(i-1,j)+diff
어 제 는 팔 지 말고 오늘까지 남 겨 두 어 라
그러나 사실 첫 번 째 상황 은 고려 할 필요 가 없다.왜냐하면 당일 에 팔 면 이윤 이 증가 하지 않 고 완전히 중복 작업 이기 때문이다.이런 상황 은 global[i-1][j-1]에 요약 할 수 있 기 때문에 우 리 는 max(0,diff)가 필요 하지 않다.그러면 두 가지 모두 diff 를 더 해서 우 리 는 diff 를 max 의 밖으로 뽑 을 수 있 기 때문에 업 데 이 트 된 전달 공식 은 다음 과 같다.
local[i][j] = max(global[i - 1][j - 1], local[i - 1][j]) + diff
global[i][j] = max(local[i][j], global[i - 1][j])
유사 한 제목:
Best Time to Buy and Sell Stock with Cooldown
Best Time to Buy and Sell Stock IV
Best Time to Buy and Sell Stock II
Best Time to Buy and Sell Stock
참고 자료:
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
C++가 LeetCode(123.주식 을 사 는 가장 좋 은 시간 3)를 실현 하 는 것 에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++가 주식 을 사 는 가장 좋 은 시간 3 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 우 리 를 많이 지 켜 주시 기 바 랍 니 다!