> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/highway-billboard-problem.md).

# 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  
```

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


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mayanktyagi3111.gitbook.io/interview-prep/dynamic-programming/highway-billboard-problem.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.