fork download
copy 
  1. #include<stdio.h>
  2. int max(int a, int b)
  3. {
  4.     int max_num;
  5.     return (a>b ? a:b);
  6.  
  7. }
  8. int maxSubArrayProd(int a[], int size)
  9. {
  10.    int max_so_far = 1;
  11.    int i;
  12.    //stores number of negative entries
  13.    int num_of_neg=0;
  14.    //stores first negative entries if any
  15.    int first_neg;
  16.    //stores last negative entries if any
  17.    int last_neg;
  18.    int prod_so_far_right_of_last_neg=1;
  19.    int prod_so_far_left_for_first_neg=1;
  20.    int prod_so_far_left=1;
  21.    int prod_so_far_right=1;
  22.    int prod_so_far_middle=1;
  23.    int prod_right_of_last_neg=1;
  24.    int prod_left_of_last_neg=1;
  25.    int prod_left_of_first_neg=1;
  26.    int prod_right_of_first_neg=1;
  27.  
  28.    for(i = 0; i < size; i++)
  29.    {
  30.        if (a[i] < 0)
  31.        {
  32.            if (num_of_neg == 0) {
  33.                first_neg = i;
  34.            }
  35.            num_of_neg++;
  36.            last_neg = i;
  37.        }
  38.    }
  39.    if ((num_of_neg%2 == 0) || (num_of_neg == 0)) {
  40.        //multiply all
  41.        for(i = 0; i < size; i++)
  42.        {
  43.         max_so_far *= a[i];
  44.        }
  45.        return max_so_far;
  46.    } else if (num_of_neg == 1) {
  47.        //only one negative number
  48.        //find prod of left and write numbers
  49.        for(i = 0; i < first_neg; i++)
  50.        {
  51.         prod_so_far_left *= a[i];
  52.        }
  53.        for(i = first_neg+1; i < size; i++)
  54.        {
  55.         prod_so_far_right *= a[i];
  56.        }
  57.        return max(prod_so_far_left, prod_so_far_right);
  58.    } else {
  59.        //more than one odd negative numbers
  60.        for(i = 0; i < first_neg; i++)
  61.        {
  62.         prod_so_far_left_for_first_neg *= a[i];
  63.        }
  64.        for(i = first_neg+1; i < last_neg; i++)
  65.        {
  66.         prod_so_far_middle *= a[i];
  67.        }
  68.        for(i = last_neg+1; i < size; i++)
  69.        {
  70.         prod_so_far_right_of_last_neg *= a[i];
  71.        }
  72.        prod_left_of_first_neg = prod_so_far_left_for_first_neg;
  73.        prod_right_of_first_neg = prod_so_far_middle * prod_so_far_right_of_last_neg * a[last_neg];
  74.        prod_left_of_last_neg = prod_so_far_left_for_first_neg * a[first_neg] * prod_so_far_middle;
  75.        prod_right_of_last_neg = prod_so_far_right_of_last_neg;
  76.  
  77.        return (max(max(prod_right_of_last_neg, prod_left_of_last_neg),
  78.                    max(prod_right_of_first_neg, prod_left_of_first_neg)));
  79.    }
  80. }
  81.  
  82. /*Driver program to test maxSubArraySum*/
  83. int main()
  84. {
  85.    int a[] = {-2, -3, 4, 0, -2, 1, 5, -3};
  86.    int max_prod = maxSubArrayProd(a, 8);
  87.    printf("Maximum contiguous prod is %d\n", max_prod);
  88.    return 0;
  89. }
Success #stdin #stdout 0s 1832KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Maximum contiguous prod is 0
https://ideone.com/o8g7Rl
language:
C (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!