# [LC] 53. 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.

Example 1:

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

Example 2:

```Input: nums = 
Output: 1
```

Example 3:

```Input: nums = 
Output: 0
```

Example 4:

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

Example 5:

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

Constraints:

• `1 <= nums.length <= 3 * 104`
• `-105 <= nums[i] <= 105`

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