LC053 - Maximum Subarray

Problem

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

Example

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.

Solution

Naive

Calculate the sum of every possible subarray, which is cubic $O(n^3)$ since we have n operations iterating the start index, n times for the end index, and n operations to calculate the sum itself from the available indices.

Improved

Subarrays are supersets of smaller subarrays, so we don't have to calculate the results from scratch, reducing the time complexity to $O(n^2)$.

Greedy

Consider the current accumulated sum, if it is positive, then include it in the result, if it is negative, just start the subarray in the following. The time complexity of this solution is $O(n)$.

def maxSubArray(self, nums: List[int]): -> int:
	ptr = 0
	tally = 0
	maxSub = nums[0]
	
	while ptr < len(nums):
		if tally < 0:
			tally = 0
		tally += nums[ptr]
		maxSub = max(maxSub, tally)
		ptr += 1
		
	return maxSub