[LeetCode] 53. Maximum Subarray

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

Maximum Subarray - LeetCode

문제 유형 : 다이나믹 프로그래밍 / 카데인 알고리즘

문제 난이도 : Medium

 

문제

Given an integer array nums, find the subarray with the largest sum, and return its sum.

 

nums 라는 int 배열이 주어진다. 이 배열의 가장 큰 부분합의 최대값을 구해라.

 

 

풀이

카데인 알고리즘으로 해결할 수 있다. 이전의 부분합에 다음 수만 더해보는 방식이고, 더한 뒤, 이전의 부분합들 중 최대와 비교해나가면 문제를 해결할 수 있다.

 

코드(C++)

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        if(n == 1) return nums[0];
        if(*max_element(nums.begin(), nums.end()) < 0) return *max_element(nums.begin(), nums.end());
        int curr_sum = nums[0];
        int max_sum = nums[0];

        for (int i = 1; i < n; i++) {
            curr_sum = max(nums[i], curr_sum + nums[i]);
            max_sum = max(max_sum, curr_sum);
        }

        return max_sum;
    }
};