Maximum Contiguous Subsequence Sum in Quadratic 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 two for loops gives the solution so it is a quadratic O(n²) solution to maximum contiguous subsequence sum in quadratic time in Java.

Removing one of the extra for loops also helps to get rid of expensive operations so the quadratic time becomes preferable to cubic time solution.

package basics;

public class MaxSubSumQuadratic {

 public static int maxSubSum(int[] inArr) {

  int maxSum = 0;

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

    if (thisSum > maxSum)
     maxSum = thisSum;
    
   }   
  }

  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 MaxSubSumQuadratic.java file in your workspace.

When the main method inside the MaxSubSumQuadratic 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)