3-2-子数组最大乘积

 1 /*
 2     思路：
 3         因为每个元素可正可负可0，所以在arr数组每个位置i处记录当前乘积的max和min，
 4         而位置i+1处乘积的max/min就只有三种可能：
 5             1) max*arr[i+1];
 6             2) min*arr[i+1];
 7             3) arr[i+1].
 8         因此每次在位置i处记录成绩的最大值并更新，最终返回即可。
 9 */
10 #include <iostream>
11 #include <vector>
12 #include <math.h>
13 using namespace std;
14 
15 double Max(double a, double b){
16     return a>b?a:b;
17 }
18 double Min(double a, double b){
19     return a<b?a:b;
20 }
21 double maxProduct(vector<double> arr){
22     if (arr.size() == 0)
23         return 0;
24     double max = arr[0];
25     double min = arr[0];
26     double res = max;
27     for (int i = 1; i < arr.size(); i++){
28         double maxa = max*arr[i];
29         double mina = min*arr[i];
30         max = Max(Max(maxa, mina), arr[i]);
31         min = Min(Min(maxa, mina), arr[i]);
32         res = Max(res, max);
33     }
34     return res;
35 }
36 
37 int main(){
38     vector<double> a;
39     /*a.push_back(-2.5);
40     a.push_back(4);
41     a.push_back(0);
42     a.push_back(3);
43     a.push_back(0.5);
44     a.push_back(8);
45     a.push_back(-1);*/
46     a.push_back(0.1);
47     a.push_back(0.0);
48     a.push_back(3);
49     a.push_back(-2.0);
50     a.push_back(0.9);
51     a.push_back(-1.3);
52     a.push_back(5.0);
53     a.push_back(-4.4);
54     cout << maxProduct(a) << endl;
55     return 0;
56 }