[cut-rod]

import java.io.IOException;

class type {

    static int cut_rod(int p[], int n) {
        if (n == 0)
            return 0;
        int q = -1;
        for (int i = 1; i <= n; i++)
            q = Math.max(q, p[i] + cut_rod(p, n - i));
        return q;
    }

    static int memoized_cut_rod(int p[], int n) {
        int[] r = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            r[i] = -1;
        }
        return memoized_cut_rod_aux(p, n, r);
    }

    private static int memoized_cut_rod_aux(int[] p, int n, int[] r) {
        /**
         * use r with lenght n or length n+1
         */
        if (r[n] > 0)
            return r[n];
        int q;
        if (n == 0)
            q = 0;
        else {
            q = -1;
            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;
    }

    private static int bottom_up_cut_rod(int p[], int n) {
        int[] r = new int[n + 1];
        r[0] = 0;
        for (int j = 1; j <= n; j++) {
            int q = -1;
            for (int i = 1; i <= j; i++)
                q = Math.max(q, p[i] + r[j - i]);
            r[j] = q;
        }
        return r[n];
    }

    public static void main(String args[]) throws NumberFormatException,
            IOException {
        int[] p = { 0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30 };
        int r = 4;
        int result;
        // result = cut_rod(p,r);
        // result = memoized_cut_rod(p, r);
        result = bottom_up_cut_rod(p, r);
        System.out.println(result);
    }
}