@ bharat, koup
Sorry I missed this condition...
Algo can tweaked little bit further to cover all conditions..
Algorithm-->
1. Find out start and end index of contiguous subarray which* has sum >0 *
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...
Check out the code...Time Com.. O(n) Space O(1)
compare result of 2 and 3 and choose d best one...
public class LongestConArrMaxAvg{
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_ending_here>0) {
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 = {7,10,-1};
maxAvgSum(a, 5);
}
}
On Fri, Nov 23, 2012 at 4:14 PM, bharat b <[email protected]>wrote:
> @ 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 <
> [email protected]> 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 <
>> [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
>>
>> --
>>
>>
>>
>
> --
>
>
>
--
Regards,
Sachin Chitale
Application Engineer SCJP, SCWCD
Contact# : +91 8086284349, 9892159511
Oracle Corporation
--
