# 53. Maximum Subarray (1)

[Link](https://leetcode.com/problems/maximum-subarray/submissions/)

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

**Example:**

```
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
```

**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.

**Soluition**

Dp作法是將問題簡化成 當下的最大sum會等於(之前的最大sum+目前的number

```
class Solution {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        //dp表示每個index的最大sum值
        //dp[i] = dp[i-1] + nums[i] 當dp[i-1] > 0,
        //若nums[i] < 0, 那就是dp[i] = dp[i-1]，因為加上nums[i]反而使sum變小
        int[] dp = new int[len];
        int maxValue = Integer.MIN_VALUE;
        for(int i = 0; i < nums.length; i++){
            dp[i] = nums[i] + ((i != 0 && dp[i-1] > 0) ? dp[i-1] : 0);
            maxValue = Math.max(maxValue, dp[i]);

        }
        return maxValue;
    }
}
```
