Maximum product of a consecutive sequence of an array of integers without zero

 Problem 
#include <stdio.h>

typedef struct {
int start, end, product;
}Ret;


Ret maxProduct(int a[], int n) {

Ret r = {0, n - 1, 1};


int i = n, j, p1, p2;

while(i--)
r.product *= a[i];

if(r.product > 0)
return r;


//need to eliminate one negative number at the beginning or at the end

p1 = p2 = r.product;

for( i = 0 ; i < n && a[i] > 0; ++i)
p1 /= a[i];

p1 /= a[i];

for(j = n -1; j >= 0 && a[j] > 0; --j)
p2 /= a[j];

p2 /= a[j];


if(p1 >= p2) {
r.start = i + 1;
r.product = p1;
} else {
r.end = j - 1;
r.product = p2;
}


return r;

}

int main() {
int n;

scanf("%d", &n);

int a[n];

int i;

for(i = 0; i <n; ++i)
scanf("%d", a + i);


Ret r = maxProduct(a, n);


printf("%d %d %d\n", r.start, r.end, r.product);

return 0;
}
Advertisements

One thought on “Maximum product of a consecutive sequence of an array of integers without zero

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s