# Billboard challenge algorithm

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 <= N <= 100,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)
{
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;
}


Code:

#include<stdio.h>
#include<stdlib.h>

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

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

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

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

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

long returnValue(long i, long j)
{
if(i<=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):

• use a while(<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