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 <= N <= 100,000 (10^5)
1 <= K <= N
0 <= profit value of any billboard <= 2,000,000,000 (2 * 10^9)

My solutio

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(






• 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

StackExchange Code Review Q#17808, answer score: 2