Skip to main content
1 of 2
paramar
  • 137
  • 6

Largest subarray with average < k

I try to solve this problem. The algorithm I developped has a complexity of $O(n^2)$. When dealing with large data the program is brought to its knees. Do you have any idea that might be faster than a quadratic algorithm? I summarize the problem briefly: Let A be a one dimensional array containing both positive and negative values, and also suppose a k. What we are searching is the size of the biggest subarray whose average is bigger than k or even equal. k is an integer and the array contains only integers.
For example if k=0 and A[] = -8 3 -1 -1 -1 -1 -1 2 -11. The output should be 7 (from A[2] to A[8].
Another simpler example 1 10 -1 -1 4 -1 7 2 8 1 . The output should be 3.

paramar
  • 137
  • 6