Maximum Contiguous Subarray Sum

Rajeev SinghAlgorithms1 mins read

Maximum Contiguous Subarray Sum problem statement

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.

Maximum Contiguous Subarray Sum solution in Java

This problem can be solved using Kadane’s algorithm in O(n) time complexity.

The algorithm iterates over all the elements of the array (nums) and computes the maximum sum ending at every index (maxEndingHere). Here is how maxEndingHere is calculated:

  • Initialize maxEndingHere to nums[0]

  • Iterate through the array (1..n). For every iteration:

    • If maxEndingHere + nums[i] < nums[i], that means the previous max was negative and therefore we reset maxEndingHere to nums[i].

    • Otherwise, we set maxEndingHere = maxEndingHere + nums[i]

  • We also keep a variable maxSoFar which indicates the maximum sum found so far. And, with every iteration, we check if the current max (maxEndingHere) is greater than maxSoFar. If yes, then we update the value of maxSoFar.

Here is the complete solution:

import java.util.Scanner;

class MaximumSubarray {

  private static int findMaxSubarraySum(int[] nums) {
    int n = nums.length;
    int maxSoFar = nums[0];
    int maxEndingHere = nums[0];

    for(int i = 1; i < n; i++) {
      if(maxEndingHere + nums[i] < nums[i]) {
        maxEndingHere = nums[i];
      } else {
        maxEndingHere = maxEndingHere + nums[i];
      }

      if(maxEndingHere > maxSoFar) {
        maxSoFar = maxEndingHere;
      }
    }
    return maxSoFar;
  }

  public static void main(String[] args) {
    Scanner keyboard = new Scanner(System.in);
    int n = keyboard.nextInt();
    int[] nums = new int[n];
    for(int i = 0; i < n; i++) {
      nums[i] = keyboard.nextInt();
    }

    System.out.println(findMaxSubarraySum(nums));
  }
}
# Output
$ javac MaximumSubarray.java
$ java MaximumSubarray
9 -2 1 -3 4 -1 2 1 -5 4
6

Maximum Contiguous Subarray with Indices

It’s also possible to find out the start and end indices of the maximum contiguous subarray. Here is a modification of the above program which does that and prints the subarray -

import java.util.Scanner;

class MaximumSubarray {

  private static int[] findMaxSubarrayIndices(int[] nums) {
    int n = nums.length;
    int maxSoFar = nums[0];
    int maxEndingHere = nums[0];
    int currentStart = 0, maxStart = 0, maxEnd = 0;

    for(int i = 1; i < n; i++) {
      if(maxEndingHere + nums[i] < nums[i]) {
        maxEndingHere = nums[i];
        currentStart = i;
      } else {
        maxEndingHere = maxEndingHere + nums[i];
      }

      if(maxEndingHere > maxSoFar) {
        maxSoFar = maxEndingHere;
        maxStart = currentStart;
        maxEnd = i;
      }
    }

    return new int[]{maxStart, maxEnd};
  }

  public static void main(String[] args) {
    Scanner keyboard = new Scanner(System.in);
    int n = keyboard.nextInt();
    int[] nums = new int[n];
    for(int i = 0; i < n; i++) {
      nums[i] = keyboard.nextInt();
    }

    int[] indices = findMaxSubarrayIndices(nums);
    int sum = 0;
    System.out.print("Max contiguous subarray: ");
    for(int i = indices[0]; i <= indices[1]; i++) {
      System.out.print(nums[i] + " ");
      sum += nums[i];
    }
    System.out.println();
    System.out.println("Max contiguous subarray sum: " + sum);
  }
}
# Output
$ javac MaximumSubarray.java
$ java MaximumSubarray
9 -2 1 -3 4 -1 2 1 -5 4
Max contiguous subarray: 4 -1 2 1
Max contiguous subarray sum: 6