How can I improve my Algorithm?

Question

This is a problem from Interview Street in Dynamic Programming section. https://www.interviewstreet.com/challenges/dashboard/#problem/4f2c2e3780aeb

Billboards(20 points)

ADZEN is a very popular advertising firm in your city. In every road you can see their advertising billboards. Recently they are facing a serious challenge , MG Road the most used and beautiful road in your city has been almost filled by the billboards and this is having a negative effect on the natural view.

On people's demand ADZEN has decided to remove some of the billboards in such a way that there are no more than K billboards standing together in any part of the road.

You may assume the MG Road to be a straight line with N billboards.Initially there is no gap between any two adjecent billboards.

ADZEN's primary income comes from these billboards so the billboard removing process has to be done in such a way that the billboards remaining at end should give maximum possible profit among all possible final configurations.Total profit of a configuration is the sum of the profit values of all billboards present in that configuration.

Given N,K and the profit value of each of the N billboards, output the maximum profit that can be obtained from the remaining billboards under the conditions given.

Constraints
1 <= N <= 1,00,000(10^5)
1 <= K <= N
0 <= profit value of any billboard <= 2,000,000,000(2*10^9)

My Solution (Psuedocode):

Let Profit[i] denote the Profit from ith billboard.
(i, j) denotes the range of billboards
MaxProfit(i, j) for all (i, j) such that i<=j and i-j+1 <= K is:
    MaxProfit(i, j) = Profit[i] + Profit[i+1] + ... + Profit[j];

For other (i,j) MaxProfit equals,

MaxProfit(i, j)
{
        if(MaxProfit(i, j) is already calculated)
            then return its value;
    max = 0;
    for all k such that i<=k<=j // k denotes that, that position has no   billboard
    {
        temp = MaxProfit(i, k-1) + MaxProfit(k+1, j);
        if(temp > max)
        max = temp;
    }
return max;
}

My solution is of order $$N^2$$. So I get TLE and Segmentation fault for larger N. I have already passed 6/10 test cases. I need to pass remaining 4. Help needed.

Answer 1

You can do it in $O(N \log N)$ time and $O(N)$ space.

Instead of finding the billboards that you want to keep, find the billboards that you want to get rid of. You need to find the minimum cost set of billboards such that there is no gap of more than $K$ between two billboards. Do this by constructing a table where the $i$th entry is the minimum cost to remove the $i$th billboard and enough previous billboards to make this legal. Now, to add an entry to the table, you need to find the minimum of the previous $K$ entries to the table. You can do this in $O(\log N)$ time using a priority queue.

If $K \ll N$, you might want to use a fancier priority queue that takes $O(\log K)$ time instead; but I'd guess that for large $K$, the simpler priority queues such as heaps that don't admit deletion of a non-MIN item are quicker for this problem. I don't know how tight time limits Interview Street has set for this problem.