[Leetcode] 53. Maximum Subarray 문제풀이

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

Maximum Subarray - LeetCode

 

문제 내용

연속된 부분 집합의 합이 최대인 값을 구하는 문제

 

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]

Output: 6

Explanation: [4,-1,2,1] has the largest sum = 6.

 

문제 풀이

연속된 값만 구하면 된다.

연속해서 합했을 때 현재 값보다 크면 계속 더하고

현재 값보다 작으면 현재값으로 업데이트하는 방식으로 쭉 나가면 된다.

 

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int sum = nums[0];
        int ans = sum;
        for (int i = 1; i < nums.size(); ++i) {
            sum = max(sum + nums[i], nums[i]);
            ans = max(ans, sum);
        }
        return ans;
    }
};