[leetcode 53] Maximum Subarray

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

 

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.

Example 2:

Input: nums = [1] Output: 1

Example 3:

Input: nums = [0] Output: 0

Example 4:

Input: nums = [-1] Output: -1

Example 5:

Input: nums = [-2147483647] Output: -2147483647

 

풀이:

얼마전에 풀었던 문제와 비슷하지만 이번엔 연속 최대 합 찾는 문제이다.

생각보다 쉬웠다.

dp[i]는 i를 포함한 계산 값 중 큰 값을 의미한다. max(누적합 + cur, cur)

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int dp[n];
        
        memset(dp, 0, sizeof(dp));
        
        dp[0] = nums[0];
        int answer = dp[0];
        for(int i=1; i<n; i++){
            dp[i] = max(nums[i], dp[i-1] + nums[i]);
            answer = max(answer, dp[i]);
        }
        return answer;
    }
};