Maximum sum contiguous sub-array

You are provided with an array of integers. We need to find the sub-array with the maximum sum such that all the elements are contiguous.

Example:
Input: [-2, -5, 6, -2, -3, 1, 5, -6]
Output: 7
Explanation: The sub-array with maximum sum is [6, -2, -3, 1, 5]

Problem Statement:

You are provided with an array of integers. These elements could be all positive, all negative or a combination of both. A sub-array is a smaller array formed using the elements of the original array. The condition for this problem is that the elements of the sub-array should be contiguous. Out of all the contiguous sub-arrays possible we need to find the maximum sum that can be formed. Also note that the sub-array that forms the maximum sum could also be a single element. For example, if all the elements are negative, except one; then that would be the maximum sum.

Brute Force Method:

We first try to come up with a solution that works, and then try to optimize it. It seems that if we are able to find all the possible sub-arrays, we can calculate the sum formed by each of them. Once we have those sums, it is very easy to point out the sub-array with the maximum sum. Hence, the most naive approach would look something like:

• Start two loops.
• The outer loop picks up elements one by one.
• The inner loop traverses till the end and keeps a track of the sum formed by sub-arrays.
• At the same time we keep on updating the maximum sum found.
• Once the outer loop ends, we have the maximum possible sum.

This approach works perfectly and would give us a correct solution but the time complexity would be O(n^2). If the array size is small (~50 elements), then we wouldn’t mind using it but the number of sub-arrays could just explode in case of larger arrays.

Optimized approach:

To understand the optimized approach this problem, let me try to break it down into several parts. The array defined in the problem statement when indexed would look something like this.

Instead of thinking in the forward direction, let us try to look in reverse. To explain things better, take up the array element “A[3] = -2”. What could be the sum of all possible sub-arrays that end at this element?

For all contiguous sub-arrays that end at A[3], the maximum possible sum is 4. Next, let us look at all the possible sub-arrays that end at “A[4] = -3”

In this case, the maximum sum that we could find was “1”. But think for a moment, do we actually have to calculate all the sums again? If we already had the maximum sum possible up to A[3] (which was 4) we could easily just try adding A[4] to the maximum sum obtained so far, and update the maximum possible sum.

This gives a very important hint at how to solve the problem. If we are able to maintain the maximum possible sum at every given position, we just need to append the next element and only update the maximum sum if it is greater than the previous one. Using these deductions, we can come up with an algorithm, also known as Kadane’s algorithm.

Algorithm:

1. Initialize 2 variables max_so_far = 0 and curr_max = 0.
2. Start a loop for each element of the array
3. At each step, find the maximum value between curr_max and (curr_max + A[i])
4. Update max_so_far if it is smaller than curr_max.
5. At the end of the loop, you would have the value of maximum sum in max_so_far

Code:

  public int maxSubArray(int[] nums) {

    // To find the maximum sum possible
    int max_so_far = nums[0];

    // To store the maximum found at a position
    int curr_max = nums[0];

    for (int i = 1; i < nums.length; i++) {

      // Equivalent to step 3
      curr_max = Math.max(nums[i], nums[i] + curr_max);

      // Equivalent to step 4
      max_so_far = Math.max(curr_max, max_so_far);
    }

    return max_so_far;
  }
Code language: Java (java)

Space Complexity: O(1)
Time Complexity: O(n)

You can find a working solution here.
The code is also available on Github.
A similar problem can be found on Leetcode.

Video Explanation: