// 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)
// and O(n^2) algorithms
public class RodCutting {

    // recursize solution
    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;
    }

    // top-down with memoization dynamic programming solution
    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;
    }


    // bottom-up dynamic programming solution
    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';  // indent

	for(int i = 1; i <= n; i++){
	    q[i] = p[i] + CUT_ROD2(p, n - i, recursionStr);
	    qMax = Math.max(qMax, q[i]);
	}

	// Display q's indices
	System.err.print(recursionStr +  "  ");
	for(int i = 1; i <= n; i++){
	    if(i < 10){
		System.err.print(" ");
	    }
	    System.err.print(i + " ");
	}
	System.err.println("");

	// Display q's values
	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];
    }
}