编程之美2.13 子数组最大乘积

问题描述：

给定一个长度为N的整数数组，只允许用乘法，不能用除法，计算任意（N-1）个数的组合乘积中最大的一组，并写出算法的时间复杂度。

解法：

1.暴力解法------O(n^2)

2.前后缀法------O(n)

3.统计法--------O(n)

具体思路和代码：

1.暴力解法：

思路：利用两层循环，依次删掉一个，其余的做乘法，计算出最大的。

代码：

 1 int s1(int A[], int n)
 2 {
 3     int s = 1;
 4     int max;
 5     for(int i = 1; i < n; i++)
 6     {
 7         s *= A[i];
 8     }
 9     max = s;
10     for(int i = 1; i < n; i++)
11     {
12         s = 1;
13         for(int j = 0; j < i; j++)
14             s *= A[j];
15         for(int j = i + 1; j < n; j++)
16             s *= A[j];
17         if(max < s)
18             max = s;
19     }
20     return max;
21 }

2.前后缀法------O(n)

思路：第一遍循环记录i前面所有数字的积 s[i]

第二遍循环记录i后面所有数字的积 t[i]

　　　最后一遍循环计算s[i] * t[i]，找出最大的。

代码：

 1 int s2(int A[], int n)
 2 {
 3     vector<int> s;
 4     s.push_back(1);
 5     vector<int> t;
 6     t.push_back(1);
 7     int f = 1;
 8     for(int i = 1; i < n; i++)
 9     {
10         f *= A[i-1];
11         s.push_back(f);
12     }
13     f = 1;
14     for(int i = n - 2; i >= 0; i--)
15     {
16         f *= A[i+1];
17         t.push_back(f);
18     }
19     reverse(t.begin(),t.end());
20     int max = s[0] * t[0];
21     for(int i = 1; i < n; i++)
22     {
23         if(max < (s[i] * t[i]))
24             max = s[i] * t[i];
25     }
26     return max;
27 }

3.统计法

思路：

根据数组中正负数以及0的个数分情况讨论

（1）：若有两个及两个以上0，则返回0。

（2）：若有奇数个负数，但不存在0，则去掉最大的负数。

（3）：若有奇数个负数，且存在一个0，则返回0。

（4）：若有偶数个负数，但不存在0，则去掉最小的正数。

（5）：若有偶数个负数，且存在一个0，则去掉0。

综上所述，我们在扫描一次的时候要记录0的数目，奇数的数目，最大负数，最小正数。

代码：

 1 int s3(int A[], int n)
 2 {
 3     int num0 = 0;
 4     int num_1 = 0;
 5     //这里假设数组中的正数不全小于-1000
 6     int max = -1000;
 7     //这里假设数组中的正数不全大于1000
 8     int min = 1000;
 9     for(int i = 0; i < n; i++)
10     {
11         if(A[i] == 0)
12             num0++;
13         else
14         {
15             if(A[i] < 0)
16             {
17                 num_1++;
18                 if(A[i] > max)
19                     max = A[i];
20 
21             }
22             else
23             {
24                 if(A[i] < min)
25                     min = A[i];
26             }
27         }
28     }
29     /*
30     分情况讨论
31     */
32 
33     //若有两个及两个以上0，则返回0。
34     if(num0 > 1)
35         return 0;
36 
37     //若有奇数个负数，但不存在0，则去掉最大的负数。
38     if((num_1 % 2) & (num0 == 0))
39     {
40         int sum = 1;
41         for(int i = 0; i < n ; i++)
42         {
43             if(A[i] != max)
44                 sum *= A[i];
45         }
46         return sum;
47     }
48 
49     //若有奇数个负数，且存在一个0，则返回0。
50     if((num_1 % 2) & (num0 == 1))
51         return 0;
52 
53     //若有偶数个负数，但不存在0，则去掉最小的正数。
54     if(((num_1 % 2) == 0) & (num0 == 0))
55     {
56         int sum = 1;
57         for(int i = 0; i < n ; i++)
58         {
59             if(A[i] != min)
60                 sum *= A[i];
61         }
62         return sum;
63     }
64 
65     //若有偶数个负数，且存在一个0，则去掉0。
66     if(((num_1 % 2) == 0) & (num0 == 1))
67     {
68         int sum = 1;
69         for(int i = 0; i < n ; i++)
70         {
71             if(A[i] != 0)
72                 sum *= A[i];
73         }
74         return sum;
75     }
76 }

我的代码可能存在一些冗余，这里就不优化了，有兴趣的同学可以试试，我这里主要是讲解题思路。