Billboard challenge algorithm This is a problem from Interview Street in Dynamic Programming section.


  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.
  
  Input description 
  
  1st line contain two space separated integers N and K. Then follow N
  lines describing the profit value of each billboard i.e ith line
  contains the profit value of ith billboard.
  
  Sample Input

6 2 
1
2
3
1
6
10 

  
  Sample Output

21

  
  Explanation
  
  In given input there are 6 billboards and after the process no more
  than 2 should be together.
  
  So remove 1st and 4th billboards giving a configuration _ 2 3 _ 6 10
  having a profit of 21. No other configuration has a profit more than
  21. So the answer is 21.
  
  Constraints

1 &lt;= N &lt;= 100,000 (10^5)
1 &lt;= K &lt;= N
0 &lt;= profit value of any billboard &lt;= 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&lt;=j and i-j+1 &lt;= K is:
    MaxProfit(i, j) = Profit[i] + Profit[i+1] + ... + Profit[j];

For other (i,j) MaxProfit equals,

MaxProfit(i, j)
{
    max = 0;
    for all k such that i&lt;=k&lt;=j // k denotes that, that position has no   billboard
    {
        temp = MaxProfit(i, k-1) + MaxProfit(k+1, j);
        if(temp &gt; max)
        max = temp;
    }
    return max;
}


Code:

#include&lt;stdio.h&gt;
#include&lt;stdlib.h&gt;

long **DP;
long returnValue(long i, long j);
int main()
{
    long N, K;
    scanf("%ld", &amp;N);
    scanf("%ld" ,&amp;K);

    DP = (long**) malloc(sizeof(long *) * N);

    long ARR[N];
    long j, z, i=0;
    for(i=0;i&lt;N;i++)
    {
        DP[i] = (long*)malloc(sizeof(long) * N);
        scanf("%ld", &amp;ARR[i]);
    }


    for(i=0;i&lt;N;i++)
    {
        long sum=0;
        for(j=1;j&lt;=K &amp;&amp; (i+j-1)&lt;N;j++)
        {
            sum += ARR[i+j-1];
            DP[i][i+j-1] = sum;
        }
    }

    for(j=K+1;j&lt;=N;j++)
    {
        for(i=0;i&lt;=N-j;i++)
        {
            long max = 0;
            for(z=i;z&lt;=i+j-1;z++)
            {
                long temp = returnValue(i, z-1) +     returnValue(z+1, i+j-1);
                if(temp &gt; max)
                    max= temp;
            }
            DP[i][i+j-1] = max;
        }
    }
    printf("%ld\n", DP[0][N-1]); 
    for(i=0;i&lt;N;i++)
    {
            free(DP[i]);
    }
    free(DP);
}

long returnValue(long i, long j)
{
    if(i&lt;=j)
    {
        //printf("%d\n", DP[i][j]); 
        return DP[i][j];
    }
    else
        return 0;
}


My solution is of order O(N2). So I get TLE and Segmentation fault for larger N. I have already passed 6/10 test cases. I need to pass remaining 4.
The inputs have to be limited with constraints you have listed, then


use a TreeSet to store the N objects in it 
remove the K first  
print the Set


few lines in Java (no malloc problem, memory managed by JVM): 


read the first input
use String.split() the line,
use Integer.valueOf(String) to convert
compare N,K and stop if not correct or if negative
use a while(&lt;N) for input,
test limits of input whith if and negative values
you can use toString() to print the Set, but you have to use a 
foreach to sum the result 
print result