Highway Billboard Problem

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