leetcode 121 문제 (최대 부분 배열)

121. Best Time to Buy and Sell Stock
해당 문제의 요구사항을 분석하자면.

• 무작위로 숫자배열이 할당 된다.
• 해당 배열에서 최소값 x 선정한다
• 최댓값 y를 선정하되, 해당 인덱스를 x의 인덱스보다 높은 값이여야한다.
• y-x의 값이 최대일때를 구하라.

대략적으로 설명하면 되도록 최솟값에 사서 비쌀때 팔아 최대한 많은 이득을 얻을수 있는 시기를 구하는 알고리즘 문제이다.

처음엔 몇시간정도 "이것은 마치 주식처럼 저점에 사셔 고점에 파는 그런건가?" 그럼 그래프같은걸 구현해서 계산하는건가? 라고 생각하면서 고민하다가, 알고리즘 초급 문제에 그런것까진 아니라고 생각하곤 예전에 알고리즘 관련 책에서 최대 부분 배열을 봤던걸 생각하여, 그걸로 해결하기로 했다.

책에는 4가지 방식이 있었는데, 그중 제일 성능이 좋은 O(n) 알고리즘으로 작성하여 제출하였다.

#include<algorithm>

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        vector<int> buf;
        
        int pre = prices[0];

        for(int index = 1;index < prices.size();index++) {
            buf.push_back(prices[index] - pre);
            pre = prices[index];
        }
        int sum = 0;
        int res = 0;
        for(auto &data :buf) {
            sum = max(data,data + sum);
            res = max(res,sum);
        }
        return res;
    }
};

이 알고리즘은 카데인 알고리즘이라고 불리고 있으며 동적 프로그래밍을 이용한 알고리즘인데, 어떤 배열의 부분배열의 합이 S[n]일때, S[n]의 최대 부분 배열은 (S[1],S[2],...,S[n-1])중 하나다 라는 공식을 이용하는 알고리즘이다.