INOI 2011, IOI Traning Camp 20xx

1

Problem link : Question Paper (PDF), Problem 2 is the problem I need help with

Hey, can anybody help me with solving this problem?
I have thought of an algorithm to solve this problem. Refer below.

  1. First, find the max subarray with Kadane’s. If that’s the full array, we are done.
  2. Otherwise, we, now expand our reach of the max sum by moving left and right, one by one, excluding negative values.

But now I am having some problems.

  1. How do we move ahead, that is, what is the next step in the above algorithm. There are some cases where few negative numbers are still left and it is wise to exclude them or that the sum of the rest positive elements suffices to “deal with” the remaining negative values, so we should include all of the array or some more portion of the array.
  2. What if there are more than one segments with sum equalling max sum?

Can anybody please provide me with the correct algorithm to solve this problem and a possibly, pseudocode on how to code this problem (assume c++ stl).

Thanks

2

Ig dynamic programming works.

DP(n, k) => we’re at position n and can skip up to k more elements

Dp(n, k) = max(
dp(n-1, k-1) {we choose to skip current element},
dp(n-1, k) + Value(n) { take current element},
0 {we stop out segment here} )

For final answer take max of dp(y, K) where y ranges from 1 to N

I’m not sure though if it’s allowed to take a segment of length 0 so this solution might be slightly off

3

Does anyone have testcases for this problem

4

Wont the answer be dp(y, K, end) where y ranges from 1 to N and end ranges from y to N. Because we also have to stop the sequence somewhere. We don’t need to continue it till N.

5

What? 10char

6

Solution:

n,k = map(int,input().split())
l = []
l.append(0)

for i in range(n):
    x = int(input())
    l.append(x)

best = [[0 for z in range(k+1)] for zz in range(n+1)]

for i in range(1, n+1):
    best[i][0] = max(best[i-1][0]+l[i], l[i])

    for j in range(1, min(i+1, k+1)):
        best[i][j] = max(best[i-1][j]+l[i], best[i-1][j-1])

ans = 0
for i in range(1, n+1):
    ans = max(ans, best[i][k])

print(ans)
7

Solution: testcases · GitHub