Consider an array of N integers. Find the longest contiguous sub array so that the average of its elements is greater (or equal) than a given number k.

We can reduce this problem to longest contiguous sub array with sum >= 0 by subtracting k from all values in O(n) time

public static int maxSubSum3( int [ ] a )

{

int maxSum = 0;

int thisSum = 0;

for( int i = 0, j = 0; j < a.length; j++ )

{

thisSum += a[ j ];

if( thisSum > maxSum )

{

maxSum = thisSum;

seqStart = i;

seqEnd = j;

}

else if( thisSum < 0 )

{

i = j + 1;

thisSum = 0;

}

}

return maxSum;

}

## No comments:

Post a Comment