Maximum Subarray

53. Maximum Subarray

Difficulty: Easy

Related Topics: Array, Divide and Conquer, Dynamic Programming

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example 1:

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

Example 2:

Input: nums = [1] Output: 1 Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8] Output: 23 Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

First Attempt:

Code:

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max = nums[0]
        for start in range(len(nums)):
            n = start+1
            sumNums = 0
            if start+1 == len(nums):
                if nums[start] >= max:
                    max = nums[start]
            else:
                while n < len(nums)+1:
                    sumNums = sum(nums[start:n])
                    if sumNums > max:
                        max = sumNums
                    n+=1
        return max

Feedbacks:

It gives me a time limit exceed error. So I should find an algorithm with better time complexity.

Second Attempt:

Get the sum elements one by one from the beginning and if I get negative sum, I reset the sum to zero and start again, because subarray with sum of negative numbers will not contribute to max sum of subarray. And compare current sum and max sum to get the final max sum.

Code:

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maxSum = nums[0]
        curSum = 0

        for n in nums:
            if curSum < 0:
                curSum = 0
            curSum += n
            maxSum = max(maxSum, curSum)
        return maxSum

Feedbacks:

It solves the question well. Beats 77% with runtime, but memory occupation needs improvement which only beats 11% of total submissions.