# 0053. Maximum Subarray

{% tabs %}
{% tab title="❓ Problem Statement" %}

> Source: [LeetCode - Maximum Subarray](https://leetcode.com/problems/maximum-subarray/)\
> GitHub: [Solution / Performance](https://github.com/yylou/leetcode/tree/main/0053-maximum-subarray)

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

{% tab title="✍🏻 Constraints & Example" %}
**Constraints:**

* `1 <= nums.length <= 3 * 10^4`
* `-10^5 <= nums[i] <= 10^5`

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

Input: nums = [1]
Output: 1

Input: nums = [5,4,-1,7,8]
Output: 23
```

{% endtab %}
{% endtabs %}

{% tabs %}
{% tab title="💡 Ideas" %}
{% hint style="info" %}
Whenever you see a question that asks for the **maximum or minimum of something**, **consider Dynamic Programming** as a possibility.
{% endhint %}

The difficult part is to figure out **whether a negative number is "worth" keeping in a subarray**. We could use the concept **localMax and globalMax** to find out.&#x20;

* **localMax = current sum = previous sum + nums\[i]**\
  If current sum is smaller than a new number, we take new number as current sum.\
  Otherwise, we keep adding this new number to the current sum.<br>
* **globalMax = max sum = final answer**\
  We check whether localMax (or current sum) is larger than the globalMax in each iteration. If so, we have new value of max sum
  {% endtab %}
  {% endtabs %}

{% tabs %}
{% tab title=" 🤖 Python3" %}

```python
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # (base case)
        if len(nums) == 1: return nums[0]
        
        # ==================================================
        #  Array + Dynamic Programming                     =
        # ==================================================
        # time  : O(n)
        # space : O(1)
        
        curSum = maxSum = nums[0]
        
        for i in range(1, len(nums)):
            curSum = max(nums[i], curSum + nums[i])
            maxSum = max(curSum, maxSum)

        return maxSum
```

{% endtab %}

{% tab title=" 🤖 Java" %}

```java
class Solution {
    /**
     * @time  : O(n)
     * @space : O(1)
     */

    public int maxSubArray(int[] nums) {
        /* base case */
        if(nums.length == 1) return nums[0];
    
        int curSum = nums[0], maxSum = nums[0];
        
        for(int i=1 ; i<nums.length ; i++){
            curSum = Math.max(nums[i], curSum + nums[i]);
            maxSum = Math.max(curSum, maxSum);
        }
        
        return maxSum;
    }
}
```

{% endtab %}
{% endtabs %}