# 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⁵</code>
- <code>-10⁴ <= nums[i] <= 10⁴</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

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++

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))

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

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++

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