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

Question

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.

Comments

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 ?

---

Arshad .. its about maximum about product.So,
 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".

Answer 1

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;
}

Comments

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.