[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: 6 Explanation: [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 * 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.
![](https://ikwhanchang.com/wp-content/uploads/2021/02/image-11-1024x822.png)
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.
![](https://ikwhanchang.com/wp-content/uploads/2021/02/image-12-1024x886.png)
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.