Maximum Contiguous Subsequence Sum in Cubic 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.

Three different indexes defined to solve this problem which are i,j and k respectively.

Because of there are 3 for loops used to solve its time complexity is O(n³).

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

package basics;

public class MaxSubSumCubic {

 public static int maxSubSum( int[] inArr )
 {
  int maxSum = 0;
  
  for (int i = 0; i < inArr.length; i++) {
   for( int j=i; j<inArr.length; j++ )
   {
    int currentSum = 0;
    
    for( int k=i; k<= j; k++ )
     currentSum += inArr[k];
    
    if( currentSum > maxSum )
     maxSum = currentSum;
   }
  }
  
  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 MaxSubSumCubic.java file in your workspace.

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