C program to find out the maximum product using subarray of the given array?

+1 vote
809 views

Given an array of integers (possibly some of the elements negative), write a C program to find out the *maximum product* possible by adding 'n' consecutive integers in the array, n <= ARRAY_SIZE.

Also give where in the array this sequence of n integers starts.

posted Sep 23, 2014

Any expected complexity???
No,no complexity issue..Looking for best solution
Can you provide the some two different input..
and their expected output.
20 , -5, 50, 0 , 6, -12, 2
like numbers can be negative, positive or can be 0.
so the expected ans should be : 50 + 0 + 6 = 56
and the sequence start at n = 3  (if counting as 1, 2, 3, not 0, 1, 2 ..)
Am I right ?
50*0*6 will be 0...
Sorry my bad. As per your question,
"write a C program to find out the *maximum product* possible by adding 'n' consecutive integers in the array".

+1 vote

Check the following solution, simple and iterative. (credit: http://www.geeksforgeeks.org/maximum-product-subarray/ - done one change in the code, i.e. max value is initialized to 0 in place of 1.)

``````int min(int x, int y)
{
return x < y? x : y;
}

int max(int x, int y)
{
return x > y? x : y;
}

int max_product_subarray(int localarr[], int n)
{
int max_ending_here = 1;
int min_ending_here = 1;
int max_value_so_far = 0;

/* Traverse throught the array. Following values are maintained after the ith iteration:
max_ending_here is always 1 or some positive product ending with localarr[i]
min_ending_here is always 1 or some negative product ending with localarr[i] */

for (int i = 0; i < n; i++)
{
/* If this element is positive, update max_ending_here. Update
min_ending_here only if min_ending_here is negative */
if (localarr[i] > 0)
{
max_ending_here = max_ending_here*localarr[i];
min_ending_here = min (min_ending_here * localarr[i], 1);
}

/* If this element is 0, then the maximum product cannot
end here, make both max_ending_here and min_ending_here 0
Assumption: Output is alway greater than or equal to 1. */
else if (localarr[i] == 0)
{
max_ending_here = 1;
min_ending_here = 1;
}

/* If element is negative. This is tricky
max_ending_here can either be 1 or positive. min_ending_here can either be 1
or negative.
next min_ending_here will always be prev. max_ending_here * localarr[i]
next max_ending_here will be 1 if prev min_ending_here is 1, otherwise
next max_ending_here will be prev min_ending_here * localarr[i] */
else
{
int temp = max_ending_here;
max_ending_here = max (min_ending_here * localarr[i], 1);
min_ending_here = temp * localarr[i];
}

// update max_value_so_far, if needed
if (max_value_so_far <  max_ending_here)
max_value_so_far  =  max_ending_here;
}

return max_value_so_far;
}
``````
answer Sep 24, 2014
Thanks Sir for your prompt response.
But min_ending_here i guess giving wrong value..In example:
20 , -5, 50, 0 , 6, -12, 2.
min_ending_here should be -5000.. According to above program it is returning -144.
And could you please tell me logic of where this sequence of max product starts.
Many many thanks once again :)
Answer is coming correct as 50 check the http://codepad.org/M1m6O7wb
Yeah sir true.. Answer is correct..
Sorry, I have misinterpreted it, I  thought min_ending_here and max_ending_here are for index which will point to integers which is last in subarrays of min_product and max_product .
And could you please tell me logic of where this sequence of max product starts.
Similar Questions