RodCutting.java

packagecom.thealgorithms.dynamicprogramming;

/**
 * A DynamicProgramming solution for Rod cutting problem Returns the best
 * obtainable price for a rod of length n and price[] as prices of different
 * pieces
 */
publicclassRodCutting {

privatestaticintcutRod(int[] price, intn) {
int[] val = newint[n + 1];
val[0] = 0;

for (inti = 1; i <= n; i++) {
intmax_val = Integer.MIN_VALUE;
for (intj = 0; j < i; j++) {
max_val = Math.max(max_val, price[j] + val[i - j - 1]);
 }

val[i] = max_val;
 }

returnval[n];
 }

// main function to test
publicstaticvoidmain(String[] args) {
int[] arr = newint[] { 2, 5, 13, 19, 20 };
intresult = cutRod(arr, arr.length);
System.out.println("Maximum Obtainable Value is " + result);
 }
}