top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

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

+1 vote
1,448 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 by Aarti Jain

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button
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".

1 Answer

+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 by Salil Agrawal
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
+8 votes

Divide the array in two subarrays of n/2 sizes each such that the difference of the sum of two subsets is as minimum as possible. If n is even, then sizes of two subarray must be n/2 and if n is odd, then size of one subarray must be (n-1)/2 and size of other subset must be (n+1)/2.

+5 votes

Given an unsorted array, find the max length of subsequence in which the numbers are in incremental order.

For example: If the input array is {7, 2, 3, 1, 5, 8, 9, 6}, a subsequence with the most numbers in incremental order is {2, 3, 5, 8, 9} and the expected output is 5.

...