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_far0){
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.comjavascript:
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_Algorithmhttp://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
--
