Maximum Subarray Sum

Given an integer array nums, 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: [4,-1,2,1] has the largest sum = 6.

Please check the following Algorithm for a better understanding :

int [] arr  =  {2, -9, 5, 1, -4, 6, 0, -7, 8};

In this case, the output sub-array Starts from the value 5 (index position: arr[2]) and ends with value 8 (index position: arr[8]). Check the following step by step calculation. The following figure is describing the desired subarray only.

Maximum sub-array Sum

Approach 1: Greedy

Intuition

The problem to find maximum (or minimum) element (or sum) with a single array as the input is a good candidate to be solved by the greedy approach in linear time.

Pick the locally optimal move at each step, and that will lead to the globally optimal solution.

The algorithm is general and straightforward: iterate over the array and update at each step the standard set for such problems:

  • current element
  • current local maximum sum (at this given point)
  • Theglobal maximum sum is seen so far.

If all are negative numbers then keep track of the minimum negative number. Because that will be our max subarray sum. Following is the Java implementation.

class Solution {

    public static void main(String[] args) {
        int[] arr = {0, -1};
        System.out.println(maxSubArray(arr));
    }

    public static int maxSubArray(int[] nums) {
        if (nums == null) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        int curSum = 0;
        int maxSum = 0;
        boolean isAllNegative = true;
        int minNegative = Integer.MIN_VALUE;

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

            // We found a positive number or a zero in the array
            if (nums[i] >= 0 && isAllNegative) {
                isAllNegative = false;
            }

            /**
             * Track the minimum negative number in the array
             * when all array numbers are negative
             */
            if (nums[i] < 0 && nums[i] > minNegative && isAllNegative) {
                minNegative = nums[i];
            }

            // Adding array elements one by one
            curSum += nums[i];

            // Replace currentSum with 0 when it becomes less than 0
            if (curSum < 0) {
                curSum = 0;
            }
            // Replace the maximum sum when the current sum is greater.
            // Means we have a new sub-array with greater sum
            if (maxSum < curSum) {
                maxSum = curSum;
            }
        }
        return isAllNegative ? minNegative : maxSum;
    }
}

Complexity Analysis:

  • Time complexity: O(N) since it’s one pass along the array.
  • Space complexity: O(1), since it’s a constant space solution.

Approach 2: Dynamic Programming (Kadane’s Algorithm)

The problem to find a sum or maximum or the minimum in an entire array or in a fixed-size sliding window could be solved by the Dynamic Programming (DP) approach in linear time.

There are two standard DP approaches suitable for arrays:

  • Constant space one. Move along the array and modify the array itself.
  • Linear space one. The first move in the direction left->right, then in the direction right->left. Combine the results.

Let’s use here the first approach since one could modify the array to track the current local maximum sum at this given point.

The next step is to update the global maximum sum, knowing the local one.

Maximum sub array Sum by Kadane’s Algorithm
class Solution {
  public int maxSubArray(int[] nums) {
    int n = nums.length, maxSum = nums[0];
    for(int i = 1; i < n; ++i) {
      if (nums[i - 1] > 0) nums[i] += nums[i - 1];
      maxSum = Math.max(nums[i], maxSum);
    }
    return maxSum;
  }
}

Complexity Analysis

  • Time complexity: O(N) since it’s one pass along the array.
  • Space complexity: O(1), since it’s a constant space solution.

Categories: Dynamic Programming

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s