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.

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).

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.

Ah, cool idea. Yeah, I get it now.

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]);