my wrong I guess yr 3rd point takes care of this... apologies On Fri, Aug 5, 2011 at 11:03 AM, Arun Vishwanathan <[email protected]>wrote:
> it is difficult to read code and understand but based on the logic u > mentioned in 3 points i just want to know if u also have taken care of the > case where > u have zero points in the array and as u say find each product around 0 > points, do u check within each subarray around the zero point if the number > of negative numbers is even or odd there? in case u have cool but it takes > time to sit and understand someone else's code hence am just asking > > On Thu, Aug 4, 2011 at 5:58 PM, Thayumanavar S <[email protected]>wrote: > >> > given an array containing +ve n -ve numbers , can someone give >> > efficient algo to find the max cont subarray product. >> >> this is same as problem http://online-judge.uva.es/p/v110/11059.html. >> here is the code for this one: >> #include <cstdio> >> #include <iostream> >> #include <algorithm> >> #include <limits.h> >> using namespace std; >> /* Algorithm: >> 1. if there is no zero in the array, the number of negative >> number is even, >> max product would be product of all numbers. >> 2. so we partition array around zero points and calculate each >> subarray max product >> and max product would be the subarray which has max value among >> this. >> 3. if in the subarray, the number of negative number is odd, >> then we need to leave out >> -ve number either on left or right depending on which has >> lesser absolute value. >> */ >> >> long long int >> submaxproduct(int *a, int start, int end); >> long long int >> maxprod(int *a, int n) >> { >> >> long long int maxprod = INT_MIN; >> long long int maxarrprod = 0; >> int start=0,i; >> if ( a == NULL || n == 0 ) return 0; >> for ( i = 0; i < n; i++ ) { >> if ( a[i] == 0 ) { >> if ( i != 0 && a[i-1] != 0 ) { maxarrprod = >> submaxproduct(a, start, i-1); >> if ( maxarrprod > maxprod ) >> maxprod = maxarrprod; } >> start = i+1; >> } >> else if ( i == n-1 ) { >> maxarrprod = submaxproduct(a, start, i); >> if ( maxarrprod > maxprod ) >> maxprod = maxarrprod; >> } >> } >> if ( maxprod < 0 ) maxprod = 0; >> return maxprod; >> } >> long long int >> submaxproduct(int *a, int start, int end) >> { >> int lprod=1,rprod=1; >> int lneg=0,rneg=0; >> long long int mprod=1; >> int count=0; >> int i; >> for ( i = start; i<=end;i++ ) >> { >> mprod *= a[i]; >> if ( a[i] > 0 && lneg == 0 ) >> lprod *= a[i]; >> else if ( a[i]>0 && rneg != 0 ) >> rprod *= a[i]; >> else if ( a[i] < 0 && lneg != 0 ) { >> count++; >> rneg = a[i]; >> rprod = 1; >> } >> else if ( a[i] < 0 ) { >> count++; >> lneg = rneg = a[i]; >> } >> } >> if ( ( count > 0 && (end-start) == 0) || count%2 == 0 ) >> return mprod; >> else { >> long long int maxf = max(rneg*rprod,lneg*lprod); >> return mprod/maxf; >> } >> } >> int >> main() >> { >> int n; >> int count = 1; >> int i; >> while ( cin>>n ) { >> int a[n]; >> for ( i = 0; i < n; i++ ) { >> cin >>a[i]; >> } >> printf("Case #%d: The maximum product is >> %lld.",count++,maxprod(a,n)); >> printf("\n\n"); >> } >> >> return 0; >> } >> >> >> thayumanavar s >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
