Maximum Contiguous Subsequence Sum in Linearithmic Time Recursively in Java

There are different solutions to maximum subsequence sum problem with varying complexities such as linear, quadratic and cubic.

There is also a linearithmic solution for the maximum subsequence sum problem implemented in Java.

This linearithmic solution is achieved by applying a divide-and-conquer algorithm design strategy.

Algorithm divides the input array into two different parts from the middle and then searches the max sum
1-) in the first half
2-) in the second half
3-) in the sub array that crosses the mid point of the array

1st and 2nd cases are achieved with recursive calls.

3rd case is achieved by as described at :

"by finding the largest sum in the first half that includes the last element in the first half, and the largest sum in the second half that includes the first element in the second half."

package basics;

public class MaxSubSumLinearithmic {

 public static int maxSubSum(int[] inArr) {
  return maxSubSum( inArr, 0, inArr.length-1 );
 }

 public static int maxSubSum(int[] inArr, int left, int right) {

  if (left == right)
   if (inArr[left] > 0)
    return inArr[left];
   else
    return 0;

  int mid = (left + right) / 2;
  int maxLSum = maxSubSum( inArr, left, mid);
  int maxRSum = maxSubSum( inArr, mid+1, right);

  int maxLBorderSum = 0, leftBorderSum = 0;
  for (int i = mid; i >= left; i--) {
   leftBorderSum += inArr[i];
   if ( leftBorderSum > maxLBorderSum )
    maxLBorderSum = leftBorderSum;
  }

  int maxRBorderSum = 0, rightBorderSum = 0;
  for (int i = mid + 1; i <= right; i++) {
   rightBorderSum += inArr[i];
   if ( rightBorderSum > maxRBorderSum )
    maxRBorderSum = rightBorderSum;
  }

  return getMax3( maxLSum, maxRSum, maxLBorderSum+maxRBorderSum );
 }
 
 private static int getMax3( int a, int b, int c )
 {
      return a > b ? a > c ? a : c : b > c ? b : c;
 }

 public static void main(String[] args) {

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

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

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

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

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

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

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

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

Create a MaxSubSumLinearithmic.java file in your workspace.

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

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


References :

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

Divide and Conquer Solution to Max Sub Sum

Finding-maximum-contiguous-subsequence-sum-using-divide-and-conquer-approach

Max Sub Array Problem Definition from Wikipedia