Maximum sum of two intervals

2
votes

Two players A and B are playing a game with array A of N elements in which each player chooses an array interval with maximum sum.The other simultaneously chooses another interval in the same array such that both the chosen intervals follow certain rules :

  1. Two chosen intervals shouldn't have anything between them . I.e. they should not be overlapping.

  2. Two intervals chosen shouldn't be too close to each other. There must be at least K index distance between the finish of the first interval and the start of the second interval.

  3. The sum of the values in chosen intervals should be as big as possible. Or we can say both chosen intervals sum should be as large as possible.

I want sum of these two intervals.

Example :

Let N equals to 8, K equals to 3, A[] equals to {6, 6, 0, -1, 4, 0, 3, -1}. It is optimal to choose [1, 2] and [7, 7] intervals. That is the only optimal choice that we can make.

And total sum if 12(from first interval) + 6(from second interval) = 18

I know about kadane algorithm for finding maximum sum continuous subarray .But getting trouble to implement for this problem.

1
algorithm
"But getting trouble to implement for this problem" -- what kind of trouble? Please be specific. – n. 1.8e9-where's-my-share m.
I can find a single interval with maximum sum.But how to keep track of second interval at minimum K units apart simulateously. – user3080139

1 Answers

3
votes

Another user asking for a solution of a problem from active programming contest:

http://www.codechef.com/DEC13/problems/REIGN

You should be ashamed.