> 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.
