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

3 Likes
3

A similar problem appeard in jun13 DELISH

2 Likes
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): CodeChef: Practical coding for everyone
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?

1 Like
5

nice job

6

i Am getting wa…can anyone provide me any test case for which my code fails CodeChef: Practical coding for everyone