import java.util.*;
 
/**
 *
 * Assume a company buys long steel rods and cuts them into shorter rods for sale to its customers. 
 * If each cut is free and rods of different lengths can be sold for different amounts, 
 * we wish to determine how to best cut the original rods to maximize the revenue.
 *
 */
class Ideone{
 
	private static int MIN_VALUE = -23;
	public static void main(String[] args){
		int[] a = {1, 5, 8, 9, 10, 17, 17, 20};
 
		//Calculate max costs obtained if we cut rod at different lengths
		int[] maxCosts = new int[a.length+1];
		maxCosts[0] = 0;
		for(int i=1; i<=a.length; i++){
			int maxValue = MIN_VALUE;
			for(int j=0; j<i; j++){
				maxValue = max(maxValue, maxCosts[i-j-1]+a[j]); 
			}
			maxCosts[i] = maxValue;
		}
 
		System.out.println("Max value obtained is => "+ maxCosts[maxCosts.length-1]);
	}
 
	private static int max(int a, int b){
		return a>b ? a : b;
	}
}