<Hard> Best Time to Buy and Sell Stock III (LeetCode : C#)

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/

📕 문제 설명

i번째 날짜의 주식 가격을 나타내는 배열이 주어질 때 최대 이익 계산하기

(최대 2거래까지 가능)

주식 구매 후 주식 판매 식으로 진행 (여러 거래 동시에 일어나지 않는다고 생각)

• Input
  날짜 별 주식 가격 배열
• Output
  최대 이익

예제

예제 2번 설명을 보면 구매 -> 구매 -> 판매가 안된다고 나와있다. 즉, 다시 구매하기전에는 무조건 판매가 이루어져야한다.

풀이

1) 먼저 왼쪽에서 오른쪽으로 돌면서 현재 보고있는 인덱스 기준 왼쪽에서 제일 낮았던 가격으로 샀을 때 판 가격과 이전 profit중 가장 높을 수 있었던 가격 중 더 높은 가격들을 저장해둔다. (왼쪽 기준 최소를 min에 저장 후 계산 진행)
2) 오른쪽에서 왼쪽을 돌면서 left[i]에서 팔았을 때 그 뒤 오른쪽에서 profit 가장 높일 수 있는 값을 저장해둔다. (오른쪽 기준 최대를 max에 저장 후 계산 진행)

public class Solution {
    public int MaxProfit(int[] prices) {
        int n = prices.Count();
        
        int[] left = new int[n];
        int[] right = new int[n];
        
        // 현재 인덱스 기준 left에서 제일 낮은 가격으로 구매했을 때 i번째 날에서의 최대 profit 나도록 하는 값 저장
        int min = prices[0];
        for (int i = 1; i < n; i++)
        {
            min = min < prices[i] ? min : prices[i];
            left[i] = Math.Max(left[i - 1], prices[i] - min);
        }

        // left 정해졌을 때 그 기준으로 뒤 중 가장 profit 높게 만드는 값 저장
        int max = prices[n - 1];
        for (int i = n - 2; i >= 0; i--)
        {
            max = max > prices[i] ? max : prices[i];
            right[i] = Math.Max(right[i + 1], max - prices[i]);
        }

        int profit = 0;
        for (int i = 0; i < n; i++)
        {
            profit = Math.Max(profit, left[i] + right[i]);
        }

        return profit;
    }
}

결과