Q49 Highway BillBoards - Coding Ninjas Codestudio approach 2
Fri Mar 31 2023 06:21:31 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) {
//making a HM to store billboards and their revenue
HashMap<Integer,Integer> map = new HashMap<>();
for(int i = 0 ; i < billboards.length ; i++)
map.put(billboards[i],revenue[i]);
//making dp
int dp[] = new int[m+1]; //+1 for 0th mile
dp[0] = 0;
for(int i =1 ; i <= m ; i++){
//if there exists a billboard on ith mile
if(map.containsKey(i)){
int boardNotInstalled = dp[i-1];
int boardInstalled = map.get(i);
//we add dp[i- x-1] only when ith mile is greater than x+1
if(i >= x+1)
boardInstalled += dp[i- x-1];
dp[i] = Math.max(boardInstalled,boardNotInstalled);
}
else
dp[i] = dp[i-1];
}
return dp[m];
}
}
content_copyCOPY
https://www.codingninjas.com/codestudio/problems/highway-billboards_3125967
Comments