Koup, your target should be to get contiguous array which hcodeas max sum.
Then find out average and check whether its greater than given number
check out below code.
public class Kadanes {
static int maxAvgSum(int a[],int k) {
int start, end, sum, curSum = 0;
start = end = -1;
sum = 0;
for (int i = 0; i < a.length; i++) {
if (a[i] > 0) {
if (sum == 0) {
start = i;
}
sum += a[i];
end = i;
} else {
curSum = sum + a[i];
if (curSum < 0) {
start = end = -1;
sum = 0;
} else {
sum = curSum;
}
}
}
boolean flag=(sum/(end-start+1))>k?true:false;
System.out.println(start + " : " + end+" : "+ flag);
return sum;
}
It's in Java returning max sum.
Thanks,
Sachin
On Tue, Nov 20, 2012 at 10:58 PM, Koup <anastasaki...@gmail.com> wrote:
> Yeah i have worked on modifying that algorithm for some hours.But I have
> problem when the sum is negative but the next element is a positive integer
> that will make my sum correct. In that case the algorithm makes my sum zero
> cause it was negative. Any help on that?
>
>
> On Tuesday, November 20, 2012 7:17:32 PM UTC+2, Sachin Chitale wrote:
>
>> Use Kadane's algorithm to solve this with time complexity O(n) and Space
>> O(1)
>> http://www.algorithmist.com/**index.php/Kadane's_Algorithm<http://www.algorithmist.com/index.php/Kadane's_Algorithm>
>>
>> Need to modify a bit.
>>
>>
>> --
>> Regards,
>> Sachin Chitale
>> Application Engineer SCJP, SCWCD
>> Contact# : +91 8086284349, 9892159511
>> Oracle Corporation
>>
>> On Tue, Nov 20, 2012 at 10:43 PM, Koup <anasta...@gmail.com> wrote:
>>
>>> Consider an array of N integers. Find the longest contiguous subarray
>>> so that the average of its elements is greater than a given number k
>>>
>>> I know the general brute force solution in O(N^2). Is there any
>>> efficient solution using extra space?
>>>
>>> --
>>>
>>>
>>>
>>
>>
>>
>> --
>
>
>
--
Regards,
Sachin Chitale
Application Engineer SCJP, SCWCD
Contact# : +91 8086284349, 9892159511
Oracle Corporation
--
