Thursday, November 12, 2015

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 :



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

Finding Maximum of Three Integers in Java

Finding maximum of three integers problem helps to understand if-else branching and conditionals topic in a better way.

Following is the implementation of the find maximum of three integers in Java.



package basics;

public class ThreeComparator {

 public static int max3( int a, int b, int c )
 {
  if( a>b )
  {
   if( a > c )
       return a;
   else
       return c;
  }
  else if( b>c )
  {
                 return b;
  }
  else
  {
   return c;
  }
  
 }
 
 public static void main(String[] args) {
  
  int a = 4;
  int b = 3;
  int c = 5;
  
  System.out.println("Maximum of "+a+" , "+b+" and "+c+" is = "+max3( a,b,c ));
  System.out.println("Maximum of "+a+" , "+c+" and "+b+" is = "+max3( a,c,b ));
  System.out.println("Maximum of "+b+" , "+a+" and "+c+" is = "+max3( b,a,c ));
  System.out.println("Maximum of "+b+" , "+c+" and "+a+" is = "+max3( b,c,a ));
  System.out.println("Maximum of "+c+" , "+a+" and "+b+" is = "+max3( c,a,b ));
  System.out.println("Maximum of "+c+" , "+b+" and "+a+" is = "+max3( c,b,a ));
  
  System.out.println("Maximum of 4 , 5 and 4 is = "+max3( 4,5,4 ));
  System.out.println("Maximum of 41 , 41 and 41 is = "+max3( 41,41,41 ));
  System.out.println("Maximum of 11 , 21 and 31 is = "+max3( 11,21,31 ));  
 }
}



Create a ThreeComparator.java file in your workspace.

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

Maximum of 4 , 3 and 5 is = 5
Maximum of 4 , 5 and 3 is = 5
Maximum of 3 , 4 and 5 is = 5
Maximum of 3 , 5 and 4 is = 5
Maximum of 5 , 4 and 3 is = 5
Maximum of 5 , 3 and 4 is = 5
Maximum of 4 , 5 and 4 is = 5
Maximum of 41 , 41 and 41 is = 41
Maximum of 11 , 21 and 31 is = 31

Power of a Number Implementation Recursive in Java

Calculation of exponentiation returns the value of the base number a raised to the exponent n.

Following is the recursive implementation of the power method in Java.


package basics;

public class PowerCalculator {

 public static long pow(long base, int n) {
  
  if (n == 0)
      return 1;
  
  if (n == 1)
      return base;
  
  if (n%2==0)
      return pow( base*base, n/2 );
  else
      return pow( base*base, n/2 )*base;
 }

 public static void main(String[] args) {
  
  long base = 2;
  int exponent = 4;
  System.out.println("Result of "+base+" to the "+exponent+" is = "+pow( base, exponent ));
  
  base = 3;
  exponent = 5;
  System.out.println("Result of "+base+" to the "+exponent+" is = "+pow( base, exponent ));
  
  base = 5;
  exponent = 4;
  System.out.println("Result of "+base+" to the "+exponent+" is = "+pow( base, exponent ));
  
 }
}



Create a PowerCalculator.java file in your workspace.

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

Result of 2 to the 4 is = 16
Result of 3 to the 5 is = 243
Result of 5 to the 4 is = 625


References :


Exponentiation in Wiki

Math pow method

Java 7 Math.pow implementation

For big numbers you can use Java-BigInteger