Help needed in solving Table Sum problem.

general
,
1

I couldn’t figure out how to solveTable Sum problem. Anyone help me with this.

2

Make use of the fact that we can split it into two parts where each part has consecutive values.

I mean 3 4 5 | 1 2

Lets consider the left part,the first element could be called as offset,
So lets say the array given was 7 4 1 3 2 (indexing 0 based)

So for left part arr would be 7+3 4+4 1+5

Or could be said 7+offset+index. 4+offset+index 1+offset+index

Or (7+index)+offset. (4+index)+offset. (1+index)+offset

Now as u see offset is common in all so in order to find maximum of left part,its sufficient to find maximum of a[i]+i for left part

So while calculating for different permutations ur offset will change which cause a change in left part size(it will increase) ,so u can simply calculate prefix max of a[i]+i.

Similarly do for the right part(here u’ll have to calculate suffix max),and take max of both parts.

3

Look at the @ma5termind explanation for this problem on :INOI 2012 Problem 2 TableSum - general - CodeChef Discuss