@ sachin : again u misunderstood the question .. question says *longest* ..
As per u'r algo ..
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)
*NO -- > even if it satisifies, that may not be the longest *
*Ex: {7,10,-1} and k=5 => as per u'r algo .. ans would be {7,10}-> avg is
>5. But and is {7,10,-1}-> avg is >5.*
On Wed, Nov 21, 2012 at 11:51 PM, Sachin Chitale
<sachinchital...@gmail.com>wrote:
> 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 <
> sachinchital...@gmail.com> 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 <anastasaki...@gmail.com> 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
>
> --
>
>
>
--
