REIGN - TLE Max sub array problem


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:

  1. 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)

  2. 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)

  3. 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

i did by your approach now am getting wa…
http://www.codechef.com/viewsolution/3192711

@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 :slight_smile:

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…

//