# 0053. Maximum Subarray
###### tags: `Leetcode` `Medium` `Dynamic Programming` `Kadane`
Link: https://leetcode.com/problems/maximum-subarray/
## 思路
考虑以```nums[i]```为结尾的maximum subarray sum怎么算
(1)```nums[i]```+以```nums[i-1]```结尾的maximum subarray sum
(2)```nums[i]```不和任何元素结合 subarray里面只有```nums[i]```
## Code
java

class Solution {
    public int maxSubArray(int[] nums) {
        int max = nums[0];
        int prev = nums[0];
        for(int i=1; i<nums.length; i++){
            int num = nums[i];
            prev = Math.max(prev+num, num);
            max = Math.max(max, prev);
        }
        return max;
    }
}

c++

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