my solution gives tle…can someone suggest optimisation for my code?
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:)
i did by your approach now am getting wa…
@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…