---
description: '# Easy'
---

# 53. Maximum Subarray

{% hint style="info" %}
Dynamic Programming

Two variables: (1) max sum; (2) max sum including current number
{% endhint %}

![](https://3288217904-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LxJcc9A1TOyn5a5HJQ4%2F-MHny_S1DWqBt-l78gDn%2F-MHo4KKKNs2VU6abG2RF%2F1600749087530.jpg?alt=media\&token=fd975bb5-6f8e-47e5-8e28-87890a66dabd)

```python
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        m = nums[0]
        tmp = nums[0]
        for i in range(1, len(nums)):
            if tmp < 0:
                tmp = nums[i]
            else:
                tmp += nums[i]
            if tmp > m:
                m = tmp
            
        return m
```

Time complexity = $$O(n)$$ , Space complexity = $$O(1)$$ .
