Find the Maximum Subarray Sum

LeetCode#54

Given an array of integers, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example

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

Approach

Use Kadane’s algorithm, which runs in O(n) time.

Golang Code

func maxSubArray(nums []int) int {
	if len(nums) == 1 {
		return nums[0]
	}
	currentSum := nums[0]
	largestSum := nums[0]
	for right := 1; right < len(nums); right++ {
		// This line is very tricky to understand
		currentSum = max(nums[right], nums[right]+currentSum)

		if largestSum < currentSum {
			largestSum = currentSum
		}
	}
	return largestSum
}

// Utility function to return max of two integers
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

Sample runs

Input
nums =
[-2,1,-3,4,-1,2,1,-5,4]

Output
6

Expected
6

Input
nums =
[5,4,-1,7,8]

Output
23

Expected
23

Why does the simple check work?

The reason why your maxSubArray function works with a simple check is based on Kadane’s algorithm, which efficiently computes the maximum sum of a contiguous subarray in O(n) time. Here’s an explanation of how the algorithm works and why it achieves linear time complexity:

The algorithm processes each element in the input array (nums) exactly once, maintaining two variables during the iteration:

• currentSum: Tracks the maximum sum of the subarray ending at the current index.
• largestSum: Stores the overall maximum subarray sum encountered so far.

For each element nums[right], you check if extending the current subarray (i.e., adding currentSum to nums[right]) is better than starting a new subarray from nums[right] alone. This simple comparison is captured by:

currentSum = max(nums[right], nums[right] + currentSum)

This decision allows you to:

• Extend the current subarray if it results in a higher sum (i.e., nums[right] + currentSum).
• Start a new subarray if nums[right] alone is larger, indicating that extending would result in a lower sum.

By doing this in one pass through the array, you avoid needing to evaluate every possible subarray (which would take much longer) and focus only on the most promising subarray at each step.

What is the secret to completing it in O(n)?

The key to achieving O(n) time complexity lies in the following points:

a. Single iteration through the array

You only loop through the array once, using a single for loop, which takes linear time, O(n).

for right := 1; right < len(nums); right++ {
    // Updating currentSum and largestSum in constant time
}

b. Constant time operations inside the loop

Within each iteration, the operations you perform are:

• Comparing two values using max (a constant time operation, O(1)).
• Updating currentSum and largestSum (both are assignments, O(1)).

Since each element of the array is processed exactly once and only constant-time operations are performed per element, the overall complexity is O(n).

c. No nested loops or recursion

There are no nested loops or recursive calls, which ensures that the algorithm doesn’t escalate beyond linear time. It avoids recalculating subarrays from scratch by leveraging the results of previous computations (i.e., the running sum stored in currentSum).

Summary of Kadane’s Algorithm

The algorithm works because:

1. It uses a running sum (currentSum) that either grows with each new element or resets to the new element if it’s larger.
2. It keeps track of the largest sum encountered so far (largestSum).
3. The entire problem is solved in one pass through the array, making it O(n).

This efficiency is what makes Kadane’s algorithm the optimal solution for the maximum subarray problem.