子数组的最大乘积

 1 /*
 2 *给定一个长度为n的整数数组，只允许用乘法不允许用除法，计算任意(n-1)个数的子数组组合中乘积最大的一组
 3 */
 4 
 5 #include <iostream>
 6 #include <sys/types.h>
 7 #include <assert.h>
 8 using namespace std;
 9 
10 int64_t max_product(int *array, int len)
11 {
12      assert(array != NULL);
13 
14      int zero_num = 0;
15      int max_neg, min_pos;
16      min_pos = max_neg = array[0];
17      int64_t res = 1;
18 
19      /*求出数组中的0的个数
20      *求出整个数组的乘积
21      *求出数组中的最小负数和最小正数
22      */
23      for(int i = 0; i != len; ++i)
24      {
25           res *= array[i];
26           if(array[i] == 0)
27                ++zero_num;
28           else if(array[i] < 0)
29           {
30                if(array[i] > max_neg)
31                     max_neg = array[i];
32           }
33           else
34           {
35                if(array[i] < min_pos)
36                     min_pos = array[i];
37           }
38      }
39      if(res == 0)//整个数组乘积为0
40      {
41           if(zero_num >= 2)//数组里有至少两个0
42                return 0;//任一子数组乘积必为0
43           else
44           {
45                res = 1; bool b = true;
46                //除去一个0
47                for(int i = 0; i != len; ++i)
48                {
49                     if(b && array[i] == 0)
50                     {
51                          b = false;
52                          continue;
53                     }
54                     res *= array[i];
55                }
56                if(res == 0 || res < 0)
57                     return 0;
58                else if(res > 0)
59                     return res;
60           }
61      }
62      else if(res > 0)
63      {
64           res = 1;
65           //除去min_pos
66           for(int i = 0; i != len; ++i)
67           {
68                if(array[i] == min_pos)
69                     continue;
70                res *= array[i];
71           }
72      }
73      else //res < 0
74      {
75           res = 1;
76           //除去max_neg
77           for(int i = 0; i != len; ++i)
78           {
79                if(array[i] == max_neg)
80                     continue;
81                res *= array[i];
82           }    
83      }
84      return res;
85 }
86 
87 int main(int argc, char const *argv[])
88 {
89      int array[] = {0, 8, 5, 99, 10, -4, -2, 1, 55};
90      cout<<max_product(array, sizeof(array)/sizeof(int))<<endl;
91      return 0;
92 }