[LC] 53. Maximum SubarrayTech
Given an integer array
nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
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 =  Output: 1
Input: nums =  Output: 0
Input: nums = [-1] Output: -1
Input: nums = [-100000] Output: -100000
1 <= nums.length <= 3 * 104
-105 <= nums[i] <= 105
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)
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.