[Easy] Leetcode | 53. Maximum Subarray | dynamic programming

https://leetcode.com/problems/maximum-subarray/

 

- 문제
integer 배열이 nums로 주어지는데, nums의 연속적인 부분 배열의 합 중 최댓값을 찾아 반환해주는 함수를 작성하는 문제이다.
(부분 배열은 최소 1개의 요소를 가짐) 

- 풀이
연속적인 부분 배열의 최대합을 구하기 위해 다음과 같은 계획을 세웁니다.

다른 풀이 방법은 더 빠른 시간 복잡도를 가질 수 있지만, 해당 방법은 선형 시간(O(n))의 복잡도를 가진다.

1. 각 요소를 마지막 요소로 가지는 부분 배열들의 합(sum) 중 가장 큰 값을 벡터(subArrayMaxSum)에 저장한다.
    => 즉, subArrayMaxSum라는 벡터의 [i]번 째 요소엔 nums[i]를 마지막 요소로 가지는 부분 배열의 합 중 가장 큰 합이 들어있다.

2. subArrayMaxSum의 요소 중 가장 큰 값이 문제에서 원하는 부분합 중 가장 큰 값이다.  

class Solution 
{
public:
    int maxSubArray(vector<int>& nums) 
    {
        
        size_t size = nums.size();
        
        // 각 요소는 i번째 요소를 마지막으로 하는 부분합 중 가장 큰 합
        // each element is a max of sum in subarrays which have a nums[i] as last element.
        // ex) subArrayMaxSum[2]: maximum in nums {[2], [1]+[2], [0]+[1]+[2]}
        std::vector<int> subArrayMaxSum;
        subArrayMaxSum.reserve(size);

        // subArrayMaxSum[0]: [0]
        subArrayMaxSum.push_back(nums[0]);
        
        // subArrayMaxSum[1]: max([1], [0]+[1])
        // subArrayMaxSum[2]: max([2], [1]+[2], [0]+[1]+[2])
        // ...
        // subArrayMaxSum[i]: max([i], [i-1]+[i], ... , [0]+..+[i])
        
        for(size_t i = 1; i != size; ++i)
        {
            subArrayMaxSum.push_back(std::max(nums[i], subArrayMaxSum[i-1] + nums[i]));
        }
        
        // maximum in subArrayMaxSum
        return *std::max_element(subArrayMaxSum.begin(), subArrayMaxSum.end());
    }
};

 

• memoization을 위해 subArrayMaxSum[i-1]을 사용한다. 
• std::max_element() 함수는 순차적인 컨테이너의 반복자 2개를 받아 그 사이에서 가장 큰 값을 가리키는 반복자를 반환한다.