# [LC] 53. Maximum Subarray

TechGiven an integer array `nums`

, find the contiguous subarray (containing at least one number) which has the largest sum and return *its sum*.

**Example 1:**

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

**Example 2:**

Input:nums = [1]Output:1

**Example 3:**

Input:nums = [0]Output:0

**Example 4:**

Input:nums = [-1]Output:-1

**Example 5:**

Input:nums = [-100000]Output:-100000

**Constraints:**

`1 <= nums.length <= 3 * 10`

^{4}`-10`

^{5}<= nums[i] <= 10^{5}

Approach

Although it is in the “easy” category, I spent 9 hours solving it! It was too much but I think my original approach was pretty much messy. I definitely thought there is a brute force approach which was a timeout. So, I realized it should be less than O(N*N) time.

I tried to find some pattern within here. First, save all the sum into another array from [0…i] In above example (-3,4,-1,2,1,-5,4), sum array should be (-3, 1,0,2,3,-2,2) then from the first element, I just subtract that element like, subtract -3 to every [1…i] for the 1st iteration. Then subtract 1 to every [2…i] for the 2nd iteration, for the last element. It sounds like O(NlogN), but it is actually O(N*N) to not be better even I can solve this approach.

Here is my 2nd approach. I made the equation like a[0…i-1]+a[i…j]+a[j+1…n] = k (sum of all) and I was trying to have the smallest a[0…i-1] and a[j+1…n] However, I found that I don’t need to consider either a[0…i-1] or a[j+1…n] because in that case, I should keep saving at least three positions and it is redundant. Furthermore, it could not bring me any kind of insight. So, I gave up.

Lastly, I just thought that what is the “continuous” means. In the sense of continuous, I should decide either to include the next element or start from the next element based on some criteria. For example, in the above example, if I choose [-3] then the next step should be either [-3,4] or [4]. To find the criteria, I finally realized that I don’t need to save the previous sum which was my 2nd approach. I need only keep saving the sum_so_far and if I need to restart, then sum_so_far should be reset and keep saving the maximum sum_so_far. Here is my final solution:

```
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
if len(nums) == 0:
return 0
if len(nums) == 1:
return nums[0]
sum_so_far = 0
rslt = -10**5
for num in nums:
sum_so_far = max(sum_so_far + num, num)
rslt = max(rslt, sum_so_far)
return rslt
```

Time Complexity: O(N)

Space Complexity: O(1)

**Submission**

Runtime: 64 ms, faster than 79.02% of Python3 online submissions for Maximum Subarray.

Memory Usage: 14.7 MB, less than 94.57% of Python3 online submissions for Maximum Subarray.