import java.util.Random;
import java.text.DecimalFormat;
import java.util.Scanner;

public final class MaxSumTest2
{
    static private int seqStart = 0;
    static private int seqEnd = -1;

    /**
     * Cubic maximum contiguous subsequence sum algorithm.
     * seqStart and seqEnd represent the actual best sequence.
     */
    public static int maxSubSumCubic( int [ ] a )
    {
        long count = 0;
        int maxSum = 0;

        DecimalFormat fmt =  new DecimalFormat("###,###,###,###,###.##");

        for( int i = 0; i < a.length; i++ )
            for( int j = i; j < a.length; j++ )
            {
                int thisSum = 0;

                for( int k = i; k <= j; k++ )
                {
                    count++;
                    thisSum += a[ k ];
                }

                if( thisSum > maxSum )
                {
                    maxSum   = thisSum;
                    seqStart = i;
                    seqEnd   = j;
                }
            }
        System.out.println("\n\nCubic Count: " + fmt.format(count));
        return maxSum;
    }

    /**
     * Quadratic maximum contiguous subsequence sum algorithm.
     * seqStart and seqEnd represent the actual best sequence.
     */
    public static int maxSubSumQuadratic( int [ ] a )
    {
        long count = 0;
        int maxSum = 0;

        DecimalFormat fmt =  new DecimalFormat("###,###,###,###,###.##");

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

                if( thisSum > maxSum )
                {
                    maxSum = thisSum;
                    seqStart = i;
                    seqEnd   = j;
                }
            }
        }
        System.out.println("\n\nQuadratic Count: " + fmt.format(count));
        return maxSum;
    }

    /**
     * Linear-time maximum contiguous subsequence sum algorithm.
     * seqStart and seqEnd represent the actual best sequence.
     */
    public static int maxSubSumLinear( int [ ] a )
    {
        long count = 0;
        int maxSum = 0;
        int thisSum = 0;

        DecimalFormat fmt =  new DecimalFormat("###,###,###,###,###.##");

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

            if( thisSum > maxSum )
            {
                maxSum = thisSum;
                seqStart = i;
                seqEnd   = j;
            }
            else if( thisSum < 0 )
            {
                i = j + 1;
                thisSum = 0;
            }
        }
        System.out.println("\n\nLinear Count: " + fmt.format(count));
        return maxSum;
    }

    /**
     * Recursive maximum contiguous subsequence sum algorithm.
     * Finds maximum sum in subarray spanning a[left..right].
     * Does not attempt to maintain actual best sequence.
     */
    private static int maxSumRec( int [ ] a, int left, int right )
    {
        int maxLeftBorderSum = 0, maxRightBorderSum = 0;
        int leftBorderSum = 0, rightBorderSum = 0;
        int center = ( left + right ) / 2;

        if( left == right )  // Base case
            return a[ left ] > 0 ? a[ left ] : 0;

        int maxLeftSum  = maxSumRec( a, left, center );
        int maxRightSum = maxSumRec( a, center + 1, right );

        for( int i = center; i >= left; i-- )
        {
            leftBorderSum += a[ i ];
            if( leftBorderSum > maxLeftBorderSum )
                maxLeftBorderSum = leftBorderSum;
        }

        for( int i = center + 1; i <= right; i++ )
        {
            rightBorderSum += a[ i ];
            if( rightBorderSum > maxRightBorderSum )
                maxRightBorderSum = rightBorderSum;
        }

        return max3( maxLeftSum, maxRightSum,
                     maxLeftBorderSum + maxRightBorderSum );
    }

    /**
     * Return maximum of three integers.
     */
    private static int max3( int a, int b, int c )
    {
        return a > b ? a > c ? a : c : b > c ? b : c;
    }

    /**
     * Driver for divide-and-conquer maximum contiguous
     * subsequence sum algorithm.
     */
    public static int maxSubSumDivideAndConquer( int [ ] a )
    {
        return a.length > 0 ? maxSumRec( a, 0, a.length - 1 ) : 0;
    }

    /**
     * Simple test program.
     */
    public static void main( String [ ] args )
    {
        int i, n;
        int maxSum;
        Random generator = new Random();
        Scanner scan = new Scanner(System.in);
        long  startTime,  stopTime,  runTime;

        System.out.print( "\n\nEnter the size of the array: ");
        n = scan.nextInt();

        while (n > 0)
        {
           int[] a = new int[n];

           for (i = 0; i < n; i ++)
              a[i] = (generator.nextInt(100)) - 50;

           System.out.println("\n");
           if (n <= 100)
             for (i = 0; i < n; i++)
                System.out.print(a[i] + " ");
           System.out.println("\n");

           if (n >= 5000)
           {
              a[4993] =  -10000000;
              a[4994] =  100000000;
              a[4995] =  100000000;
              a[4996] =  -50000000;
              a[4997] =  100000000;
              a[4998] = -100000000;
              a[4999] =  100000001;
              a[5000] = -100000000;
           }

           DecimalFormat fmt =  new DecimalFormat("###,###,###,###,###.##");

           startTime  =  System.currentTimeMillis();
		   maxSum = maxSubSumLinear( a );
           stopTime  =  System.currentTimeMillis();
           runTime  =  stopTime - startTime;
		   System.out.println("\n\nLinear Run Time: " + runTime + " milliseconds");
           System.out.println( "\nMax sum is " + fmt.format(maxSum) + "   it goes"
                       + " from " + seqStart + " to " + seqEnd + "\n");

           startTime  =  System.currentTimeMillis();
           maxSum = maxSubSumQuadratic( a );
           stopTime  =  System.currentTimeMillis();
		   runTime  =  stopTime - startTime;
		   System.out.println("\n\nQuadratic Run Time: " + runTime + " milliseconds");
           System.out.println( "\nMax sum is " + fmt.format(maxSum) + "   it goes"
                       + " from " + seqStart + " to " + seqEnd + "\n");

           startTime  =  System.currentTimeMillis();
           maxSum = maxSubSumCubic( a );
           stopTime  =  System.currentTimeMillis();
		   runTime  =  stopTime - startTime;
		   System.out.println("\n\nCubic Run Time: " + runTime + " milliseconds");
           System.out.println( "\nMax sum is " + fmt.format(maxSum) + "   it goes"
                       + " from " + seqStart + " to " + seqEnd + "\n");

      //   maxSum = maxSubSumDivideAndConquer( a );
      //   System.out.println( "\nMax sum is " + fmt.format(maxSum) );

           System.out.print( "\n\nEnter the size of the array: ");
           n = scan.nextInt();
        }

        System.out.println("\n");
    }
}