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; } }
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