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 <thayum...@gmail.com> 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 algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
