Q49 Highway BillBoards - Coding Ninjas Codestudio (approach 1 LIS)
Fri Mar 31 2023 06:04:39 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
import java.util.* ;
import java.io.*;
public class Solution {
public static int highwayBillboard(int[] billboards, int[] revenue, int m, int x) {
/* Q49 dp playlist ,first approach same as LIS , we find max while
applying LIS here we have to make sure 2 billboards are placed at a
greater distance of x , which becomes the constraint between i and j
*/
int ans = Integer.MIN_VALUE;
int dp[] = new int[revenue.length];
dp[0]=revenue[0];
for(int i = 1 ; i < dp.length ;i++){
int profit = revenue[i];
for(int j = i-1 ; j >=0 ; j--){
int potential = dp[j] + revenue[i];
if(billboards[i] - billboards[j] > x)
profit = Math.max(potential , profit);
}
dp[i] = profit;
ans = Math.max(ans , dp[i]);
}
return ans;
}
}
content_copyCOPY
https://www.codingninjas.com/codestudio/problems/highway-billboards_3125967
Comments