Re: [algogeeks] max product of a subarray
my wrong I guess yr 3rd point takes care of this...
apologies
On Fri, Aug 5, 2011 at 11:03 AM, Arun Vishwanathan
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 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
>> #include
>> #include
>> #include
>> 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.
Re: [algogeeks] max product of a subarray
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 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
> #include
> #include
> #include
> 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.
Re: [algogeeks] max product of a subarray
> 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
#include
#include
#include
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.
