문제

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

해결 방법

• prices = [3, 2, 3, 6, 5, 4, 0, 3]으로 주어졌다면 이를 그래프로 나타내면

• 이 그래프에서 증가하는 구간들의 합을 구하면 (2~6), (0~3) 이고, 이 때 얻을 수 있는 최댓값은 4 + 3 = 7 임을 알 수 있음
  • 감소하는 구간에선 물건을 팔 수 없고, 증가하는 구간에서 가장 싸게 사서 가장 비싸게 파는 과정을 반복하여 최댓값을 구하는 방식
• 증가/감소에 따른 계산 과정을 정리하면
  1. 증가 -> 증가 : 증가 구간의 최댓값이 더 커졌으므로 구간합 갱신
  2. 증가 -> 감소 : 이전의 값이 증가 구간에서의 최댓값이므로 이전까지 구했던 구간합을 answer에 더함
  3. 감소 -> 감소 : 증가 구간의 최솟값 갱신
  4. 감소 -> 증가 : 구간합을 현재값 - 이전에 구했던 최솟값으로 갱신

코드

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;

        if (n == 1) {
            return 0;
        }

        int temp, min;
        int answer = 0;
        boolean increasing;
        if (prices[0] < prices[1]) {
            increasing = true;
            min = prices[0];
            temp = prices[1] - prices[0];
        } else {
            increasing = false;
            min = prices[1];
            temp = 0;
        }

        for (int i = 2 ; i < n ; i ++) {
            if (increasing) {
                if (prices[i] > prices[i - 1]) {
                    temp = prices[i] - min;
                } else {
                    answer += temp;
                    temp = 0;
                    min = prices[i];
                    increasing = false;
                }
            } else {
                if (prices[i] < prices[i - 1]) {
                    min = prices[i];
                } else {
                    temp = prices[i] - min;
                    increasing = true;
                }
            }
        }

        if (increasing) {
            answer += prices[n - 1] - min;
        }

        return answer;
    }
}

결과