my solution gives tle…can someone suggest optimisation for my code?
My solution-
http://www.codechef.com/viewsolution/3151583
@yagnak:
the optimum complexity of this problem is O(N) for each testcase. Ur solution is close to O(N^2)
knowing to solve Maximum subarray problem by KADANE’s ALGORITHM might be useful.
After that go through the Editorial.
I will also explain my approach:
-
calculate the maximum subarray sum at each index i, store the max(fmax[i-1],max sum at i) in fmax[i] in the forward direction i.e., (0 to n-1)
-
similarly calculate the maximum subarray sum at each index i, store the max(bmax[i+1],max subsum at i) in bmax[i] in the backward direction (n-1 to 0)
-
calculate the maximum sum of array fmax[i]+bmax[i+k+1] (for 0 to n-1-k). //fmax=maximum forward subarray sum
link to my soution.
You might also like a similar problem DELISH from JUNE13
Wishes to solve the problem:)
1 Like
@yagnak: sorry u misunderstood my approach, i edited my post(better explanation), ur working solution http://www.codechef.com/viewsolution/3197809 , post if have any doubt 
why are you finding the forward subarray till n-1…instead we should find it till n-k-1 as there has to be a difference of k between the two arrays…