coursea Interview Question
SDE1sCountry: United States
public static int maxProfit(int[] rods, int cost, int price) {
int maxProfit = Integer.MIN_VALUE;
int minLenRoad = Integer.MAX_VALUE;
for(int r: rods)
minLenRoad = Math.min(minLenRoad, r);
// if minimum value is more than 50; as per mentioned above
minLenRoad = Math.min(minLenRoad, 50);
int[][] dp = new int[rods.length][minLenRoad];
for(int i = 0; i< rods.length; i++) {
for(int j = 0; j < minLenRoad; j++) {
// rod len => j + 1;
// max profit = Number * Price * Length - cut*Cost
int n = rods[i] / (j+1);
int l = (j+1);
int c = (rods[i] % (j+1) == 0)? n-1 : n;
dp[i][j] = (n * l * price) - (c * cost);
if(i != 0) {
dp[i][j] += dp[i-1][j];
}
maxProfit = Math.max(maxProfit, dp[i][j]);
}
}
return maxProfit;
}
public static int maxProfit(int[] rods, int cost, int price) {
int maxProfit = Integer.MIN_VALUE;
int minLenRoad = Integer.MAX_VALUE;
for(int r: rods)
minLenRoad = Math.min(minLenRoad, r);
// if minimum value is more than 50; as per mentioned above
minLenRoad = Math.min(minLenRoad, 50);
int[][] dp = new int[rods.length][minLenRoad];
for(int i = 0; i< rods.length; i++) {
for(int j = 0; j < minLenRoad; j++) {
// rod len => j + 1;
// max profit = Number * Price * Length - cut*Cost
int n = rods[i] / (j+1);
int l = (j+1);
int c = (rods[i] % (j+1) == 0)? n-1 : n;
dp[i][j] = (n * l * price) - (c * cost);
if(i != 0) {
dp[i][j] += dp[i-1][j];
}
maxProfit = Math.max(maxProfit, dp[i][j]);
}
}
return maxProfit;
}
- Akhilesh Maloo January 29, 2018