REIGN - Editorial

editorial
, ,
1

PROBLEM LINK:

link:Contest

Author: @kostya_by

Tester: @white_king

DIFFICULTY:

Easy

PROBLEM:

This can be solved using dynamic programming.
Call best_forward[i] to be the maximum prosperity of a sequence that ends at i. This can be computed as:
best_forward[i]=max(A[i], best_forward[i-1] + A[i]).

From this, you may easily compute the maximum prosperity of any sequence that ends anywhere between 0…i as:
cumulative_best_forward[i] = max(cumulative_best_forward[i-1], best_forward[i]).

Similarly let best_backward[i] be the maximum prosperity of a sequence starting at i
best_backward[i]=max((ll)A[i], best_backward[i+1] + A[i]). Similarly, you compute cumulative_best_backward[i].

The answer is simply
max_{j=K+2 to N} (cumulative_best_forward[j-K-1] + cumulative_best_backward[j]).

4 Likes
2

I used the same approach. The maximum ‘prosperity’ in this problem is a popular problem - Maximum Subarray
.

Here’s my solution: REIGN

1 Like
3

A similar problem appeard in jun13 DELISH

1 Like
4

My idea is kind of similar, but not exactly the same. Instead of finding cumulative_best_forward[i] from best_forward[i] and cumulative_best_forward[i-1], I tried to directly obtain a recurrence relation for cumulative_best_forward[].

I defined two arrays - result[i] -> best sum upto i (not necessarily ending at i, exactly like cumulative_best_forward)

(a[i] is the array containing input elements)

rem[i] -> if the best sum upto i, is made by choosing the interval [j,k] 0<=j<=k<=i, then rem[i] = a[k+1]+a[k+2]+…a[i] i.e the sum of the elements to the right of the best interval, and before i which are not part of the interval (the sum of the remainder elements)

Next I wrote the following recurrence relations for the two arrays:

if (a[i+1]+rem[i] >=0 && result[i]+rem[i] >=0) { result[i+1] = result[i]+rem[i]+a[i+1]; rem[i+1] = 0; }

else if (a[i+1] >= result[i]) { result[i+1] = a[i+1]; rem[i+1] = 0; }
else {result[i+1] = result[i]; rem[i+1] = rem[i] + a[i+1];}

And after getting result[i] in the forward direction, I did the same for the backward, and looped through the input array to find the final answer.

I tried this, but my solution was not accepted (WA): http://www.codechef.com/viewsolution/3103902
Is there something wrong with my recurrence relation? I’m unable to find the mistake.
(I know it’s kind of complicated when compared to the traditional maximal sub-arrays solution, but I’m still new to DP, so I want to find the mistake in my thinking)
Can someone please help?

5

i Am getting wa…can anyone provide me any test case for which my code fails http://www.codechef.com/viewsolution/3448210

6

nice job