 # 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

@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 