You are given a rod of length N units along with an array that contains the prices of all pieces of size smaller than N (1 to N). You need to find out the maximum profit that can be obtained by cutting the rod into pieces and then selling it.
Sample Input: Prices – [ 1, 5, 8, 9, 10, 17, 17, 20 ], N = 8
Expected Output: 22
Explanation: The rod can be cut into two pieces of size 2 and 6 with total profit as 22.
Algorithm:
- We will use dynamic programming to solve this problem. Create a DP array of size N+1 intialized to 0.
- Iterate for all sizes starting from 1 to N.
- For each size, consider all sizes less than or equal to the current size.
- If we take size j ( j<=i, where i is the length of the rod ) and cut the rod into two pieces of size j and ( i – j ), the result will be maximum of DP[ i ] and ( prices[ j ] + DP[ i – j ] ). We do this for all j from 1 to i and for all i from 1 to N. We keep storing the result for each subproblem in the DP array and return the final result stored in DP[ N ].
#include <bits/stdc++.h> using namespace std; int helper(vector<int> prices, int n){ vector<int> dp(n+1, 0); for(int i=1; i<=n; i++){ for(int j=1; j<=i; j++){ dp[i] = max(dp[i], prices[j-1] + dp[i-j]); } } return dp[n]; } int main(){ vector<int> prices = {1, 5, 8, 9, 10, 17, 17, 20}; int n=4; cout<<helper(prices, n); return 0; }
Also take a look at another popular interview question Maximum Sum Subarray.
3 comments