Maximum Subarray variation

Question

I have to solve a problem much like the maximum subarray problem. I have to find the largest subarray whose average is bigger than k. I thought the following trick. I can transform my array A[] of size n to a B[] where B[i] = A[i] - k. So now the average must be >0. But average greater than zero doesnt simply mean sum greater than zero? So I can directly apply Kadane's algorithm. Am I right? (always under the constraint that there is 1 positive value)

Answer 1

no, kadane's algorithm will still find you the subarray with the biggest sum...i have to solve the same problem. so far i kave find that if we create the array B as you mentioned above and then make the array C which contains the partial sums of the array B,then the maximum interval (i,j) that we are lookink for has the same number for i and j!!! for example:

array A is: 1 10 -1 -1 4 -1 7 2 8 1 .....and the given k is 5 then array B is: -4 5 -6 -6 -1 -6 2 -3 3 -4 array C is:-4 1 -5 -11 -12 -18 -16 -19 -16 -20 so the subarray that we are looking for is [7,2,8], has length 3, and has the same first and last element which is -16!!!!

edit: i forgot to tell that we are searching for a O(n) or an O(n*logn) algorithm.... @lets_solve_it you are right but your algorithm is O(n^2) whitch is way to big for the data we want to handle. i 'm close to solve it with the function map in c++,whitch is something like a hash table. i thing this is the right diredtion because here the elements of the array C have direct relation with their indexes! Also our professor told us that another possible solution ,is to make again the array C and then take a (special?) pivot to do quicksort....but i don't totally understand what we expect from quicksort to do.

Answer 2

@panos7:

after you have created array C (partial sums array), you seek two values of C, Ci and Cj,

such that, Cj>=Ci, and, (j-i) is as "big" as possible. (j-i) --> MAX.

then return j-i.

in your example, -16>=-18 so you returned j-i=9-6=3

which is the correct answer!