I couldn’t figure out how to solveTable Sum problem. Anyone help me with this.
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.
Look at the @ma5termind explanation for this problem on :https://discuss.codechef.com/questions/60311/inoi-2012-problem-2-tablesum