**** Problem: longest sub-array having sum at most k?

If all the array elements are positive then this problem is easily solvable using two pointers. for ex:

Let's say the array look like this a=[10,30,40,7,1] and k=48.

Solution: We keep two pointers l and r and we will always expand our sub-array with rth pointer and shrink from lth pointer

Iterations:

l=0,r=0 a[l---r]= 10 since 10<=48 we update our ans as 1 and we increment the rth pointer l=0,r=1 a[l---r]= [10,30] since 10+30<=48 we update our ans as 2 and we again increment the rth pointer. l=0,r=2 a[l---r]= [10,30,40] since 10+30+40>48 we will shrink our window by incrementing the lth pointer untill sum<=k. ie [10,30,40] to [30,40] still sum>k so we reduce the window to [40] l=2,r=2 a[l----r]=40

l=2,r=3 a[l---r]= [40,7] since 40+7<=48 we increment the rth pointer l=2,r=4 a[l---r]= [40,7,1] since 40+7+1<=48 we update our answer as 3.

This problem is also covered in the two pointers section in code forces edu.

But the problem with this algorithm is it does not work if the array contains negative elements because we are not assure that shrinking the window size always make our sum less positive as our lth pointer can be very big negative value as well. Thus removing the lth pointer here makes our sum more positive.

for ex: a=[-5,-4,-3,16,1,-6,-4,50] and k=3

In above example we can clearly see that the subarray[0,6]=[-5,-4,-3,16,1,-6,-4] is longest having sum<=3

But if we go by above algorithm we will not get this as our answer because when our rth pointer reaches 16 ie a=[-5,-4,-3,16] sum=4>k so we will shrink our window to [-4,-3,16] sum=9>k again we will shrink window to [-3,16] still sum>k.At the end we will be left with empty window ie l=r=3.

Now here we will not get accurate answer as l is increased to 3.

For this problem the only solution that comes into mind is O(N*N) ie trying all poss sub-arrays and checking whether sum<=k and finding largest.

If anyone have a better way of solving this please suggest.Thanks in advance.