Solution: Maximum Subarray

Statement

Given an unsorted array nums, find the sum of the maximum sum subarray. The maximum sum subarray is an array of contiguous elements in nums for which the sum of the elements is maximum.

Constraints:

• $1 \leq$ nums.length $\leq 10^3$

• $-10^4 \leq$ nums[i] $\leq 10^4$

Solution

The maximum subarray sum problem inherently involves examining various subarrays to check if their sum is maximized, and the most convenient and efficient way to do this is using dynamic programming. The key idea is to efficiently find the maximum subarray ending at any position based on the maximum subarray ending at the previous position.

In the context of this problem, we’ll use Kadane’s algorithm. It uses the bottom-up approach of dynamic programming to solve subproblems iteratively, starting from the smallest subproblems and building up toward the larger problem. The subproblem here is to find the maximum subarray sum that ends at a specific index i. We need to calculate this for every index i in the array. The base case is the first element of the array, where both the current subarray sum and maximum subarray sum are initialized with the first element’s value. This is the starting point for solving the subproblems. We reuse the previously computed maximum subarray sum at each step to find the solution for the current subproblem.

The steps of the algorithm are given below:

• Initialize a currMax variable to keep track of the maximum sum of the current array index and another globalMax variable to keep track of the largest sum seen so far. Both variables will be initialized with the first element of nums.

• Traverse the array from the second element until the end of the array is reached.

• While traversing, if currMax is less than 0, assign it the element at the current index. Otherwise, add the element at the current index to currMax.

• Next, if globalMax is less than currMax, reassign it to currMax.

Let’s look at the illustration below to better understand the solution: