Maximum subarray value(Hacker Rank)


I solved it in O(n^2).

If there is any optimal solution please mention below

Thanks in Advance

I Think you can first pre-calculate the even some at every even index and odd sum at every odd index… using prefix array separately this will help to find desired sum in O(1)

Then Use two pointer approach in which first pointer starts from first position and second pointer starts from last position. now you start from first position and start moving forward and if at any index current possible sum increases we switch the pointers and decrease j until same situation happens for j now again switch and continue the same … and at last we will be left with the max sum possible subarray…

The real implementation may differ a bit i am not really sure… :face_with_raised_eyebrow:

1 Like

I am not able to understand. Can you explain in detail.

If possible provide code.

your approach will fail for [-1, 2,3,4,-5]