Can someone go through an efficient way of solving the first problem in today’s INOI? I just calculated the maximum sum when i is less than j and the max. sum when i is greater than j and compared both. But it was more or less a brute force algorithm, going through all the combinations.
I break up this problem into three cases: i = j, i < j, i > j. Note that I use 1-indexed arrays.
i = j:
The max for this case is just the max of all ai, i = 1 to n. This can be found in O(n);
i < j:
For each j, we find the value of i such that the sum from i to j is maximum.
sum(i, j) = a[i] + b[i + 1] + … + b[j - 1] + a[j]
= (b[1] + b[2] + … + b[j - 1] + a[j]) - (b[1] + b[2] + … b[i] - a[i])
Clearly, the first term depends only on j and the second term depends only on i. Since the second term is being subtracted, to find the maximum sum, we need to find the minimum value of the second term.
Thus the maximum sum ending at j corresponds to the minimum value of the second term for all i < j
The following snippet of code in pseudoc++ finds the maximum of all segments with i < j:
ans = -inf;
minsec = cursec = b[1] - a[1];
curfir = a[1];
for(int j = 2; j <= n; j++)
{
curfir = curfir - a[j - 1] + b[j - 1] + a[j];
ans = max(ans, curfir - minsec);
cursec = cursec + a[j - 1] + b[j] - a[j];
}
j < i
sum(i, j) = (b[1] + b[2] + … + b[j - 1] + a[j]) + (a[i] + b[i + 1] + … + b[n - 1] + b[n])
Once again, the first term depends only on j and the second term depends only on i.
let frontbest[k] = the maximum value of the first term for all i <= k
and similarly let reversebest[k] = the maximum value of the second term for j >= k.
We can compute both of the above arrays in O(n) each.
The answer for this case can be found as
for(int i = 1; i < n; i++)
{
ans = max(ans, frontbest[i] + reversebest[i + 1]);
}
Finally, the answer for the problem is the maximum of the answer for each of the three sub cases.
Edit: Does anybody have an easier solution to this problem? Mine seems quite complex in hindsight.
1 Like
Hi; my i < j solution was basically: you keep tracking of the maximum score you can have if you picked b[k] in down[k]. For a particular k, the maximum sum possible is a[k] + down[k - 1]. That seems fine to me, and ran perfectly well for subtask 3.
The only stupid mistake I did was to not tackle i > j separately, which would’ve solved all subtasks. Your solution seems the most efficient solution for i > j, to me.
The other thing I tried for i > j and i < j together was two passes of the first algorithm. That seemed fairly neat, but ended up with complications (read: bugs).
1 Like
down[k] = max(down[k - 1] + b[k], b[k]) right? This seems wrong to me somehow.
Could you elaborate on extending this for i > j?
That does seem wrong. down[k] = max(down[k - 1], a[k - 1]) + b[k] is what I did. Then, answer = max(answer, a[k] + down[k - 1]).
I basically tried the ‘copy same array twice’ trick, and then on the second iteration you’re only looking for contiguous subarrays with length <= N.
Ah yes, of course. Not sure why I was saying the other thing.
Can you elaborate further? Sorry, I have no clue what you’re talking about.
Edit: Just got an idea: you can find the segment with (i < j) having minimum value of -a[i] + b[i] + b[i + 1] + … + b[j - 1] + b[j] - a[j] and subtract this from the sum of all b[i]. Maybe that’s what you meant?
Hi; convinced by the i < j solution? No, although that struck me after the exam.
http://stackoverflow.com/questions/11610443/n-numbers-are-arranged-in-a-circle-we-need-to-find-the-maximum-sum-of-consecuti for quick description of my approach. If still not clear, I’ll do a write-up in another answer.
1 Like
Ah, cool idea. Yeah, I get it now.
1 Like
Right, should clarify—I forgot the case where [i, i + 1] can form a maximum sequence. Only needed a answer = max(answer, a[k] + a[k - 1]) along with what I said earlier.
A more elegant way is down[k] = max(down[k - 1] + b[k], a[k]);