Maximum Contiguous Subsequence Sum in Linear Time in Java

Finding the maximum contiguous subsequence sum of an array of integers among other subsequences is one of the basic problems about operations on arrays, indices and complexity analysis.

For the array {-2, -3, 4, -1, -2, 1, 5, -3}   the maximum subsequence sum contains elements
"4, -1, -2, 1, 5" so the sum = 4+(-1)+(-2)+1+5 = 7.

Using one for loop gives the solution so it is a linear O(n) solution to maximum contiguous subsequence sum in linear time in java.

In this solution inside the for loop, if the currently added item leads to a larger result then the previous maximum then this becomes the new maximum.

If the newly added item leads to a negative sum result then the current sum is assigned the "0".

This solution works for the arrays that contain at least one positive integer.

package basics;

public class MaxSubSumLinear {

 public static int maxSubSum(int[] inArr) 
 {  
  int maxSum = 0, currentSum = 0;

  for (int j = 0; j < inArr.length; j++) {
   currentSum += inArr[j];

   if ( currentSum > maxSum)
    maxSum = currentSum;
   else if ( currentSum < 0)
    currentSum = 0;
  }

  return maxSum;
 }

 public static void main(String[] args) {

  int input[] = { -2, -3, 4, -1, -2, 1, 5, -3 };

  System.out.println("Max Sub Sum Result = " + maxSubSum(input));

  input = new int[] { -2, 3, -16, 100, -4, 5 };

  System.out.println("Max Sub Sum Result = " + maxSubSum(input));

  input = new int[] { -2, 11, -4, 13, -5, 2 };

  System.out.println("Max Sub Sum Result = " + maxSubSum(input));

  input = new int[] { -15, -23, -476, -3, -292 };

  System.out.println("Max Sub Sum Result = " + maxSubSum(input));
 }

}

Create a MaxSubSumLinear.java file in your workspace.

When the main method inside the MaxSubSumLinear class executed it is going to print :

Max Sub Sum Result = 7
Max Sub Sum Result = 101
Max Sub Sum Result = 20
Max Sub Sum Result = 0

References :

Data Structures and Algorithm Analysis in Java (3rd Edition)