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 <sachinchital...@gmail.com>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 <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 > -- Regards, Sachin Chitale Application Engineer SCJP, SCWCD Contact# : +91 8086284349, 9892159511 Oracle Corporation --