# 53. Maximum Subarray (1D-dp)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-Menme5CdYeKCgdlIo4G%2F-MensBxrVRw2l3bqf29u%2Fimage.png?alt=media\&token=d1788bbb-56af-4a1a-a847-a38bc4f304d7)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-Menme5CdYeKCgdlIo4G%2F-MensFhhYFN_Xeq6OwQN%2Fimage.png?alt=media\&token=7e8d49d0-bd27-428d-9b39-f519a2c75179)

## brute force

nested for loop, find each combination, 正數起點正數結尾(優化

time: O(n^2)

## DP

經驗：從後面開始看, 固定一個數, 前面子序列會...?

ma&#x78;_&#x73;um數字(i),   **Max**( 取前面的數max\_sum_（i-1) 或不取 (會是0) )   + 自身a\[i]

1. subproblem :  maxsum(i) = Max(max\_sum(i-1), 0) + A\[i]
2. f\[i]
3. dp 方程:&#x20;

max\_sum = 自身最大 or 自身包含之前的sum的最大

f(i) = **Max(A\[i] , A\[i] + f(i-1))** , 提出 A\[i] =>

&#x20;f(i) = Max(0,  f(i-1) ) + A\[i] . =>&#x20;

也就是

```java
dp[i] = nums[i] + (dp[i-1] < 0 ? 0 : dp[i-1]);
```

&#x20;_**dp\[i-1]  < 0 的狀況 => 不取  = 0**_&#x20;



time: O(n)

space: O(n)

```java
class Solution { 
    public int maxSubArray(int[] nums) {
        // dp[i] = dp[i-1] < 0 ? 0 : dp[i-1];
        int dp[] = new int[nums.length];
        dp[0] = nums[0];
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            // dp[i] = nums[i] + (dp[i-1] < 0 ? 0 : dp[i-1]);
            // 自身最大 or 自身包含之前的sum的最大
            dp[i] = Math.max(nums[i], nums[i] + dp[i-1]);
            // dp[i] = nums[i] + Math.max(0, dp[i-1]); 提出 nums[i] 
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}
```



## DP - just use variable



```java
dp[i] = nums[i] + Math.max(0, dp[i-1]);
can be
nums[i] = nums[i] + Math.max(0, nums[i-1]);
```

time :O(n)

space: O(1)

#### see notes!

```java
class Solution { 
    public int maxSubArray(int[] nums) {
        int res = nums[0];
        int sum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            // 自身最大 or 自身包含之前的 sum 的最大
            sum = Math.max(nums[i], sum + nums[i]);
            res = Math.max(res, sum);
        }
        return res;
    }
}
```



can be also wrote like this

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