// Implementations of rod cutting algorithms from Introductions to Algorithms, 3rd Edition by Cormen et. al.
// Timing is included to show the amazing difference between an O( 2^n) algorithm and O(n^2) algorithms
public class RodCutting {

    public static int CUT_ROD( int[] p, int n){
	if( n == 0){ // cut of length 0 or no cut at all
	    return 0;
	}
	int q = Integer.MIN_VALUE; // maximum revenue for rod of length n

	// Determine the maximum revenue for each possible cuts, produces a pair of lengths i and n-i
	for( int i = 1; i <= n; i++){
	    q = Math.max(q, p[i] + CUT_ROD( p, n - i));
	}
	return q;
    }

    public static int MEMOIZED_CUT_ROD( int[] p, int n){
	int[] r = new int[n+1];
	for( int i = 0; i <= n; i++){
	    r[i] = Integer.MIN_VALUE;
	}
	return MEMOIZED_CUT_ROD_AUX(p, n, r);
    }

    public static int MEMOIZED_CUT_ROD_AUX( int[] p, int n, int[] r){
	// If the result for length n is already known, return it
	if( r[n] >= 0){
	    return r[n];
	}

	// Result unknown, so follow the same steps as in CUT_ROD
	int q;
	if( n == 0){ // cut of length 0 or no cut at all
	    q = 0;
	}else{
	    q = Integer.MIN_VALUE;
	    for( int i = 1; i <= n; i++){
		q = Math.max(q, p[i] + MEMOIZED_CUT_ROD_AUX( p, n - i, r));
	    }
	}
	r[n] = q;
	return q;
    }


    public static int BOTTOM_UP_CUT_ROD( int[] p, int n){
	int[] r = new int[n+1]; // array of maximum revenue for each length 
	r[0] = 0; // 0 length = 0 revenue

	// for each length, from the smallest to the largest, calculate the
	// maximum revenue and store it in r
	for( int j = 1; j <= n; j++){
	    int q = Integer.MIN_VALUE; // maximum revenue for length j
	    for( int i = 1; i <= j; i++){
		q = Math.max(q, p[i] + r[j - i]);
	    }
	    r[j] = q;
	}
	return r[n];
    }


    public static long CUT_ROD_TIMING( int[] p, int n){
	Timer timer = new Timer();

	timer.start();
	int r_n = CUT_ROD(p, n);
	timer.end();

	// System.err.println( "CUT_ROD(): "+ r_n);

	return timer.time();
    }

    public static long MEMOIZED_CUT_ROD_TIMING( int[] p, int n){
	Timer timer = new Timer();

	timer.start();
	int r_n = MEMOIZED_CUT_ROD(p, n);
	timer.end();

	// System.err.println( "MEMOIZED_CUT_ROD(): "+ r_n);

	return timer.time();
    }


    public static long BOTTOM_UP_CUT_ROD_TIMING( int[] p, int n){
	Timer timer = new Timer();

	timer.start();
	int r_n = BOTTOM_UP_CUT_ROD(p, n);
	timer.end();

	// System.err.println( "BOTTOM_UP_CUT_ROD(): "+ r_n);

	return timer.time();
    }


    public static void main(String[] args) {
	int[] p = new int[] {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};  // array of prices by cut length
	int n = Integer.parseInt( args[0]);     // length of the rod

	// Adjust the prices if n is larger than the set prices
	if( n >= p.length){
	    int[] pPrime = new int[n + 1];
	    int i = 0;
	    for( i = 0; i < p.length; i++){
		pPrime[i] = p[i];
	    }
	    for( ; i <= n; i++){
		pPrime[i] = p[p.length - 1];
	    }
	    p = pPrime;
	}

	long elapsed = -1;
	int maxRevenue = -1;

	System.err.println("n = "+n);

	elapsed = CUT_ROD_TIMING( p, n);
        System.err.println( elapsed + "\tnanoSeconds CUT_ROD() - Recursive top-down implementation");

	elapsed = MEMOIZED_CUT_ROD_TIMING( p, n);
        System.err.println( elapsed + "\tnanoSeconds MEMOIZED_CUT_ROD() - Top-down with memoization implementation");

	elapsed = BOTTOM_UP_CUT_ROD_TIMING( p, n);
        System.err.println( elapsed + "\tnanoSeconds BOTTOM_UP_CUT_ROD() - Bottom-up implementation");


    }


    /*
     * Verbose versions of the functions above
     */
    public static int CUT_ROD2( int[] p, int n, String recursionStr){
	System.err.println( recursionStr + "CUT_ROD2( p, "+n+")");
	if( n == 0){
	    return 0;
	}
	int[] q = new int[n + 1];
	int qMax = Integer.MIN_VALUE; // maximum revenue for rod of length n
	recursionStr += '\t';

	for( int i = 1; i <= n; i++){
	    q[i] = p[i] + CUT_ROD2( p, n - i, recursionStr);
	    qMax = Math.max( qMax, q[i]);
	}
	System.err.print( recursionStr +  "  ");
	for( int i = 1; i <= n; i++){
	    if( i < 10){
		System.err.print(" ");
	    }
	    System.err.print(i + " ");
	}
	System.err.println( "");

	System.err.print( recursionStr +  "q:");

	for( int i = 1; i <= n; i++){
	    if( q[i] < 10){
		System.err.print(" ");
	    }
	    System.err.print(q[i] + " ");
	}
	System.err.println( "");

	return qMax;
    }

    public static int MEMOIZED_CUT_ROD2( int[] p, int n){
	int[] r = new int[n+1];
	for( int i = 0; i <= n; i++){
	    r[i] = Integer.MIN_VALUE;
	}
	String recStr = "";
	return MEMOIZED_CUT_ROD_AUX2(p, n, r, recStr);
    }

    public static int MEMOIZED_CUT_ROD_AUX2( int[] p, int n, int[] r, String recStr){
	System.err.println( recStr + "MEMOIZED_CUT_ROD_AUX2(p, "+n+", r)");
	// If the result for length n is already known, return it
	if( r[n] >= 0){
	    System.err.println(recStr+"MEMOIZED_CUT_ROD_AUX2(p, "+n+", r) returning "+r[n]+" memoized");
	    return r[n];
	}

	// Result unknown, so follow the same steps as in CUT_ROD
	int q;
	if( n == 0){ // cut of length 0 or no cut at all
	    q = 0;
	}else{
	    recStr += '\t';
	    q = Integer.MIN_VALUE;
	    for( int i = 1; i <= n; i++){
		q = Math.max(q, p[i] + MEMOIZED_CUT_ROD_AUX2( p, n - i, r, recStr));
		System.err.println(recStr+"i: "+i+", q: "+q);
	    }
	}
	r[n] = q;
	System.err.println(recStr+"MEMOIZED_CUT_ROD_AUX2(p, "+n+", r) returning "+q);
	return q;
    }


    public static int BOTTOM_UP_CUT_ROD2( int[] p, int n){
	System.err.println("BOTTOM_UP_CUT_ROD2( p, "+n+")");
	int[] r = new int[n+1]; // array of maximum revenue for each length 
	r[0] = 0; // 0 length = 0 revenue

	// for each length, from the smallest to the largest, calculate the
	// maximum revenue and store it in r
	for( int j = 1; j <= n; j++){
	    int q = Integer.MIN_VALUE; // maximum revenue for length j
	    System.err.println("j: "+j);
	    for( int i = 1; i <= j; i++){
		//q = Math.max(q, p[i] + r[j - i]);
		if( q  <  p[i] + r[j - i]){
		    q = p[i] + r[j - i];
		    System.err.println("\ti: "+i+", q: "+q);
		}
	    }
	    r[j] = q;
	}
	return r[n];
    }
}