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. asked 31 Jan '15, 17:10

I break up this problem into three cases: i = j, i < j, i > j. Note that I use 1indexed 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:
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
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. answered 31 Jan '15, 17:44
1
Hi; my The only stupid mistake I did was to not tackle The other thing I tried for
(31 Jan '15, 18:44)
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?
(31 Jan '15, 19:09)
That does seem wrong. 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.
(31 Jan '15, 19:17)
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?
(31 Jan '15, 19:34)
1
Hi; convinced by the http://stackoverflow.com/questions/11610443/nnumbersarearrangedinacircleweneedtofindthemaximumsumofconsecuti for quick description of my approach. If still not clear, I'll do a writeup in another answer.
(31 Jan '15, 19:44)
1
Ah, cool idea. Yeah, I get it now.
(31 Jan '15, 20:01)
Right, should clarifyI forgot the case where [i, i + 1] can form a maximum sequence. Only needed a
(16 Feb '15, 16:25)
A more elegant way is down[k] = max(down[k  1] + b[k], a[k]);
(17 Feb '15, 17:29)
showing 5 of 8
show all
