I know it’s a Kadane’s algorithm variation. But couldn’t crack it. How to solve it?
Heres what I did -
Let us assume we have rotated the array k times so the array now looks like this(0-indexed)
Ak Ak+1 … An-1 A0 A1 … Ak-1
Now to get the maximum sum sub-array by using the properties of the original array, we can see that, it can be the maximum sum sub-array of subarray A[k,n-1] or the maximum sum sub-array of subarray A[0,k-1] or it can be the sum of max prefix sum till (k-1)th index and max suffix sum till kth index. Now the maximum sum sub-array for a range can be easily done by a segment tree, and you can precompute the max prefix sum and max suffix sum in O(n) and then just calculate the answer for each k. I hope this helps you.
1 Like
I hate to say this but the code was available on web
1 Like
My idea is to double the array(instead of rotation) and perform range maximum sum query using segment tree 
This problem is also of same type : CodeChef: Practical coding for everyone
1 Like
Awww… This makes me remember my days when I was new to cp <3 . I did this beautiful problem without segment-tree 
4 Likes
Wow great!! I was only able to do brute force . Lol
if possible please share your approach for doing this question without segment tree
3 Likes
https://www.codechef.com/viewsolution/29795868
Maybe this is helpful?
The variable names are long though…
1 Like
please explain it ones
Basically say the sequence is
-5 4 2 1.
Create a double for ease of understanding
-5 4 2 1 -5 4 2 1
Now we need maximum contigous sum in
{-5 4 2 1}, {4 2 1 -5},{ 2 1 -5 4},{ 1 -5 4 2}.
These are all present in the doubled array.
We create a barrier in the middle. The largest sequence can either be on one side, or passing through the barrier.
for the first element
{- 5 4 2 1} \\ - 5 4 2 1
This is just the normal kadane.
second
-5 {4 2 1} \\ {-5} 4 2 1
now its either just in the second set, which we can calculate for each ending, in the first set, which we can also find using kadane, or if its in both, then we subtract the largest total sum in the second set from the smallest sum in the first set to maximize the sum of the subarray.
1 Like
time complexity will be O(n^2) right?
1 Like
forward and backward kadane O(n)
maximum sum from the start O(n)
minimum sum from the end O(n)
Computing max of forward kadane, backward, and taking the difference O(n)
All actions are done independently
This one is little less obfuscated
https://www.codechef.com/viewsolution/29791709
1 Like
Thanks
1 Like
In contest time I actually edited my GSS1 solution and submitted it 
Thanks for posting your method. But, I have some trouble following the flow of your code. Can you add a few comments or point to some source that contains this method. Thanks.
I think its better to understand the logic, rather than the code.
Say seq[i] is the ith element.
create two copies(don’t really need it in the code though)
seq[0] ,seq[1] ,… ,seq[n-1] , \ \ \ \ \ \ \ \ seq[0], seq[1],…seq[n-1].
Now after i cycles, we will have the last n-i elements in the first part, and i elements in the second part.
Now we have three cases.
The maximum sum is only in the first part, only in the second part, or in both.
When its only in the first part, we can use backwards kadane to find the maximum sequence. When its only in the second part, we can use forwards kadane to calculate the maximum subsequence. When its in both, we can simply find the largest forward sum and subtract it from the smallest backwards sum.
if you are looking for a solution without segment tree
@tmwilliamlin gave a wonderful solution and i would suggest you to try that as well.
Though i used this logic to solve it and copied the code from cp-algorithms
My solution
Do check it out
2 Likes
Thanks for the clear explanation. It was very helpful. I will try to implement this method for practice.
Sure, I will check out your solution and thanks for the link.