Implementation
public class Kadanes {
static int maxAvgSum(int a[], float k) {
int max_so_far = 0, max_ending_here = 0, avg = 0, s = -1, e = -1, ts, te,
tsum;
boolean flag = false;
for (int i = 0; i < a.length; i++) {
if (max_ending_here == 0)
s = e = i;
max_ending_here = max_ending_here + a[i];
if (max_ending_here < 0) {
max_ending_here = 0;
s = e = -1;
}
if (max_so_far < max_ending_here) {
max_so_far = max_ending_here;
e = i;
}
}
if (avgGreater(max_so_far, s, e, k)){
System.out.println("Result subarray start index:" + s
+ " End index:" + e);
return max_so_far;
}
/*This will generate two sequence use optimal time complexity of this algo
is O(n)
*
*
*/
if (s >= 0 && !avgGreater(max_so_far, s, e, k)) {
max_ending_here = max_so_far;
ts = s;
te = e;
while (ts < te) {
max_ending_here -= a[ts];
if (avgGreater(max_ending_here, ts+1, te, k)) {
ts++;
System.out.println("Result subarray start index:" + ts
+ " End index:" + te);
break;
}
ts++;
}
ts = s;
te = e;
max_ending_here = max_so_far;
while (ts < te) {
max_ending_here -= a[te];
if (avgGreater(max_ending_here, ts, te-1, k)) {
te--;
System.out.println("Result subarray start index:" + ts
+ " End index:" + te);
break;
}
te--;
}
}
return max_so_far;
}
static boolean avgGreater(int sum, int s, int e, float k) {
float t= (float) (sum / (e - s + 1));
return t>=k? true : false;
}
public static void main(String[] args) {
int[] a = { 100, 10, -1, -1, 4, -1, 7, 2, 8 };
System.out.println(maxAvgSum(a, 5));
}
}
On Wed, Nov 21, 2012 at 10:07 PM, Sachin Chitale
<[email protected]>wrote:
> Hello,
>
> Algorithm-->
> 1. Find out start and end index of contiguous subarray which has max sum
> O(n)
> 2.Once u have start and end index calculate avg if it satisfies the
> condition then done O(n)
> 2.1 other wise run a loop through start to end index and remove trailing
> elements by increasing start
> 2.2 simultaneously check avg..this will lead to proper subarray.
> 3. In similar fashion start reducing end valuse keeping start
> constant.....do it sub steps of 2...
>
> compare result of 2 and 3 and choose d best one...
> give me some time to write code....
>
>
> On Wed, Nov 21, 2012 at 12:29 AM, Koup <[email protected]> wrote:
>
>> To be correct I need the longest subarray that has an average greater
>> than k but my main problem here is to find the longest one. Thank you !
>>
>> --
>>
>>
>>
>
>
>
> --
> 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
--
