> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/dynamic-programming/53.-maximum-subarray-1d-dp.md).

# 53. Maximum Subarray (1D-dp)

![](/files/-MensBxrVRw2l3bqf29u)

![](/files/-MensFhhYFN_Xeq6OwQN)

## brute force

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

time: O(n^2)

## DP

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

max*sum數字(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 方程: 

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

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

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

也就是

```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;
    }
}
```