Maximum subarray value(Hacker Rank)

1

Question:

IMG_20210312_161916
IMG_20210312_1619162000×1500 1.08 MB
IMG_20210312_161926
IMG_20210312_1619264000×3000 1.52 MB

I solved it in O(n^2).

If there is any optimal solution please mention below

Thanks in Advance

2

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
3

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

If possible provide code.

4

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

5

First of all multiply all odd index elements with -1, as we have to subtract their value.

Now the question become maximum subarray sum, but we have to find the maximum square of the sum, which will get either by maximum subarray sum or negative sum with(Max absolute value)
For maximum subarray sum use kadane
For negative sum with Max absolute value first multiple all elements with -1 and apply kadane again

1 Like
6

Great approach.

8

@shivansh_502 What is the intuition behind this approach?