I think you have misunderstood my question. I need the algorithm to produce
the longest subarray that is greater than the average. For example if the
array is 1 10 -1 -1 4 -1 7 2 8 and k = 5 then the correct answer is 3 with
the subarray being 7 2 8 .Your algorithm will produce a false since it does
the division 29/6 that is lower than k = 5 .
Τη Τρίτη, 20 Νοεμβρίου 2012 8:28:33 μ.μ. UTC+2, ο χρήστης Sachin Chitale
έγραψε:
>
> Sorry Koup,
> Plz ignore previous code, it has errors use below code
> public class Kadanes {
> static int maxAvgSum(int a[], int k) {
> int max_so_far = 0, max_ending_here = 0, c = 0;
> boolean flag=false;
> for (int i = 0; i < a.length; i++) {
> max_ending_here = max_ending_here + a[i];
> if (max_ending_here < 0)
> max_ending_here = 0;
> if (max_so_far < max_ending_here) {
> max_so_far = max_ending_here;
> c++;
> }
>
> }
> if(max_so_far>0){
> flag = (max_so_far / c) > k ? true : false;
> }
>
> System.out.println(flag);
>
> return max_so_far;
> }
>
> public static void main(String[] args) {
>
> int[] a = { -5, 6, 2, 100, 80 };
> System.out.println(maxAvgSum(a, 13));
> }
> }
>
> expln http://www.geeksforgeeks.org/archives/576
>
>
> On Tue, Nov 20, 2012 at 11:37 PM, Sachin Chitale
> <sachinc...@gmail.com<javascript:>
> > wrote:
>
>> 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 <anasta...@gmail.com <javascript:>
>> > 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
>>
>
>
>
> --
> Regards,
> Sachin Chitale
> Application Engineer SCJP, SCWCD
> Contact# : +91 8086284349, 9892159511
> Oracle Corporation
>
--
