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

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.