import java.util.ArrayList;
import java.util.List;

public class RodCuttingComplete {

    public static List<Integer> rodCutting(int[] prices, int length) {
        if (length==0) {
            return new ArrayList<Integer>();
        }

        List<Integer> maxPieces=null;
        int maxProfit=Integer.MIN_VALUE;
        for (int i=1; i<=length; i++) {
            List<Integer> pieces=rodCutting(prices, length - i);
            int profit=0;
            for (Integer p:pieces)
                profit=profit+prices[p-1];
            profit=profit+prices[i-1];
            if (profit>maxProfit) {
                maxProfit=profit;
                maxPieces=new ArrayList<Integer>();
                maxPieces.add(i);
                maxPieces.addAll(pieces);
            }
        }

        return maxPieces;
    }
    public static void main(String[] args) {
 
        int[] prices={1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
        int n=5;

       /* 
        Generate input of big size:
        int n=100;
        int [] prices = new int[100]; 
        for (int i=0; i<99; i++)
            prices[i]=i+3;
        
        Improve rodCutting algorithm by Dynamic Programming such that 
        you can use the big size input.
         */


        List<Integer>list = rodCutting(prices, n);

        System.out.println("The maximum profit is obtained if cutting pieces of following lengths: " +list );
        int profit=0;
        for (Integer l:list)
            profit=profit+prices[l-1];
        System.out.println("The value of the maximum profit is " + profit );

    }
}