Can we find the length of the longest subarray with sum>k efficiently?

general
, ,
1

Here, ‘k’ can be any integer.

My O(nlogn) solution is as follows :- Ff3CcO - Online C++0x Compiler & Debugging Tool - Ideone.com

Is there any O(n) algorithm for above?

Thanks.

Note:-
1)I’ve done my research.
2)No, this problem does not belong to any ongoing contest in the world :slight_smile:

2 Likes
2

Yes, we can! :slight_smile:

Precalc prefix and suffix negative sums sorted by sum and length. It can be done at O(n), because we add new sum to already sorted array only if this one is smaller than last.

Use two pointers technics to parse all pretenders and choose the longest.

3

can u please send the link of the question : )

4

try variant of Kadane algorithm.

5

DOES NOT WORK

6

Question is:-Superior Substring | Practice Problems
But after we reach the last step of the solution we realize that we have to find the length of the longest sub-array with sum>-2