//{ Driver Code Starts import java.io.*; import java.util.*; class RodCutting { public static void main(String args[]) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); while (t-- > 0) { int n = sc.nextInt(); int[] arr = new int[n]; for (int i = 0; i < n; i++) arr[i] = sc.nextInt(); Solution ob = new Solution(); System.out.println(ob.cutRod(arr, n)); } } } // } Driver Code Ends class Solution{ public int cutRod(int price[], int n) { /* storage and meaning - every cell denotes maximum profit if the rod had been of that length */ int dp[] = new int[n+1]; int nprice[] = new int[n+1]; //for ease of indexing //copying all prices in 1 based indexing for(int i = 1 ; i < n+1 ; i++) nprice[i] = price[i-1]; //dp of 0 is already 0 dp[1] = nprice[1]; //1 length of rod can only be sold for price of 1 length for(int i = 2 ; i < n+1 ; i++){ //storing profit when rod is not cut at all and sold at full length of i only int maxProfit = nprice[i]; //cutting rod in 1 to i-1 pieces and checking for max profit //with optimized i-j for(int j = 1 ;j < i ; j++ ) maxProfit = Math.max(maxProfit , dp[i-j] + nprice[j]); //or //this will be cutting in j and taking cartesian product of optimized j & //optimized i-j , we only have to travel till half as then pairs will get repeated // for(int j = 1 ;j <= i/2 ; j++ ) // maxProfit = Math.max(maxProfit , dp[i-j] + dp[j]); dp[i] = maxProfit; } // for(int i = 0 ; i < n+1 ; i ++) // System.out.print(dp[i] + " "); return dp[n]; } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter