#include "max_sub.h"

//  Inline function to return the maximum value of the three given.
//
inline int Max3( int a, int b, int c )
{
  if ( a>=b && a>=c ) return a;
  else if ( b >= c ) return b;
  else return c;
}

//  Inline function to return the maximum value of the two given.
//
inline int Max( int a, int b )
{
  return ( a>=b ) ? a : b;
}


//  These, in order, are the four algorithms for the maximum
//  subsequence sum problem presented in Chapter 2 of the text.
//

int
MaxSubSum1( int A[ ], int N )
{
  int This_Sum = 0, Max_Sum = 0;

  for( int i = 0; i < N; i++ )
    for( int j = i; j < N; j++ ) {
      This_Sum = 0;
      for( int k = i; k <= j; k++ )
	This_Sum += A[ k ];

      if( This_Sum > Max_Sum )
	Max_Sum = This_Sum;
    }
  return( Max_Sum );
}


int
MaxSubSum2( int A[ ], int N )
{
  int This_Sum = 0, Max_Sum = 0;

  for( int i = 0; i < N; i++ ) {
    This_Sum = 0;
    for( int j = i; j < N; j++ ) {
      This_Sum += A[ j ];

      if( This_Sum > Max_Sum )
	Max_Sum = This_Sum;
    }
  }
  return( Max_Sum );
}



int MaxSubSum3( int A[], int Left,
		int Right )
{
  int MaxLeftSum=0, MaxRightSum=0;
  int MaxLeftBorderSum=0, MaxRightBorderSum=0;
  int LeftBorderSum=0, RightBorderSum=0;
  int Center = (Left + Right) / 2;

  if ( Left == Right )  // Base Case
    return Max( A[Left], 0 );

  // Recursive calls
  MaxLeftSum = MaxSubSum3( A, Left, Center );
  MaxRightSum = MaxSubSum3( A, Center+1, Right );

  // Find the max subsequence in the left half
  // ending at the center.
  int i;
  for( i=Center; i >= Left; i-- ) {
    LeftBorderSum += A[i];
    if ( LeftBorderSum > MaxLeftBorderSum )
      MaxLeftBorderSum = LeftBorderSum;
  }

  // Find the max subsequence in the right half
  // starting at the center.
  for( i=Center+1; i<=Right; i++ ) {
    RightBorderSum += A[i];
    if ( RightBorderSum > MaxRightBorderSum )
      MaxRightBorderSum = RightBorderSum;
  }

  return Max3( MaxLeftSum, MaxRightSum,
	       MaxLeftBorderSum + MaxRightBorderSum );
}

// Driver  for the above recursive function
int MaxSubSum3( int A[], int N )
{
  return MaxSubSum3( A, 0, N-1 );
}



int
MaxSubSum4( int A[ ], int N )
{
  int This_Sum = 0, Max_Sum = 0, Seq_Start = 0;

  for( int Seq_End = 0; Seq_End < N; Seq_End++ ) {
    This_Sum += A[ Seq_End ];

    if( This_Sum > Max_Sum )
      Max_Sum = This_Sum;
    else if( This_Sum < 0 ) {
      Seq_Start = Seq_End + 1;
      This_Sum = 0;
    }
  }
  return( Max_Sum );
}