###### tags: `leetcode`
# Question 53. Maximum Subarray
### Description:
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
### Solution:

DP, when sum drops below to 0, reset sum.

### AC code

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