Consider a highway of M miles. The task is to place billboards on the highway such that revenue is maximized. The possible sites for billboards are given by number x1 < x2 < ….. < xn-1 < xn, specifying positions in miles measured from one end of the road. If we place a billboard at position xi, we receive a revenue of ri > 0. There is a restriction that no two billboards can be placed within t miles or less than it.
Note : All possible sites from x1 to xn are in range from 0 to M as need to place billboards on a highway of M miles.
Examples:
Input : M = 20
x[] = {6, 7, 12, 13, 14}
revenue[] = {5, 6, 5, 3, 1}
t = 5
Output: 10
By placing two billboards at 6 miles and 12
miles will produce the maximum revenue of 10.
Input : M = 15
x[] = {6, 9, 12, 14}
revenue[] = {5, 6, 3, 7}
t = 2
Output : 18
class Solution {
// Only take care on left, and keep moving right
public static int billboard(int M, int[] Position, int[] Profit, int minDist) {
// left[i] -> Stores the closest index on left
// which is at a distance > minDist
int[] left = new int[Position.length];
left[0] = -1;
int behind = 0;
for (int i = 1; i < Position.length; i++) {
while (Position[i] - Position[behind] > minDist)
behind++;
left[i] = behind - 1;
}
// dp[i] -> Max profit for the first 'i' billboards
int[] dp = new int[Position.length];
// Base case
dp[0] = Profit[0];
for (int i = 1; i < Position.length; i++) {
// If we dont make a billboard at ith position
dp[i] = dp[i - 1];
// If we try to make a billboard at ith position
if (left[i] != -1)
dp[i] = Math.max(dp[i], dp[left[i]] + Profit[i]);
}
return dp[Position.length - 1];
}
}