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
<[email protected]>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 <[email protected]> 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 <[email protected]> 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
--
