---
# System prepended metadata

title: LC 53. Maximum Subarray
tags: [medium, leedcode, DP, Greedy, python, c++]

---

# LC 53. Maximum Subarray

### [Problem link](https://leetcode.com/problems/maximum-subarray/)

###### tags: `leedcode` `python` `c++` `medium` `Greedy` `DP`

Given an integer array <code>nums</code>, find the subarray with the largest sum, and return its sum.

**Example 1:** 

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

**Example 2:** 

```
Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.
```

**Example 3:** 

```
Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.
```

 **Constraints:** 

- <code>1 <= nums.length <= 10<sup>5</sup></code>
- <code>-10<sup>4</sup> <= nums[i] <= 10<sup>4</sup></code>


 **Follow up:**  If you have figured out the <code>O(n)</code> solution, try coding another solution using the  **divide and conquer**  approach, which is more subtle.
## Solution 1 - DP
#### Python
```python=
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        res = nums[0]
        dp = [0] * (n + 1)
        dp[0] = nums[0]
        # dp[i]: 以nums[i]為結尾的Maximum Subarray和

        for i in range(1, n):
            dp[i] = max(nums[i], dp[i - 1] + nums[i])
            res = max(res, dp[i])

        return res
```
#### C++
```cpp=
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp(nums.size(), 0);

        dp[0] = nums[0];
        int res = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            int curSum = dp[i - 1] + nums[i];
            dp[i] = max(curSum, nums[i]);
            res = max(res, dp[i]);
        }
        return res;
    }
};
```
## Solution 2 - DP (Space Complexity: O(n))
```cpp=
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = nums[0];
        int curMax = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            curMax = max(curMax + nums[i], nums[i]);
            res = max(res, curMax);
        }
        return res;
    }
};
```

## Solution 3 - Greedy
#### Python
```python=
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        res = float("-inf")
        sum_ = 0

        for idx, num in enumerate(nums):
            sum_ += num
            if sum_ > res:
                res = sum_
            if sum_ < 0:
                sum_ = 0

        return res
```
#### C++
```cpp=
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN;
        int cnt = 0;
        for (int i = 0; i < nums.size(); i++) {
            cnt += nums[i];
            if (cnt > res) {
                res = cnt;
            }
            if (cnt < 0) {
                cnt = 0;
            }
        }
        return res;
    }
};
```

>### Complexity
>|             | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1  | O(n)            | O(n)             |
>| Solution 2  | O(n)            | O(1)             |
>| Solution 3  | O(n)            | O(1)             |


## Note
sol2:
nums = [-2,1,-3,4,-1,2,1,-5,4]
curMax = -2,
num = 1, curMax = 1
num = -3, curMax = -2
num = 4, curMax = 4
num = -1, curMax = 3
num = 2, curMax = 5
num = 1, curMax = 6
num = -5, curMax = 1
num = 4, curMax = 5
