题解 | #连续子数组的最大乘积#

#include <iostream>
#include<algorithm>
#include<string>
using namespace std;

//int dp[10000][10000];//由于最后的暴力解
int dp1[1000000];//用于存储以i结尾的连续子串的最大正数积，若该积不是正数存入该节点的值
int dp2[1000000];//用于存储以i结尾的连续子串的绝对值最大的负数积，若该积不是负数存入该节点的值
int main() {
    int n;
    cin >> n;
    int a[n];
    int tmpup, tmpdown;
    for (int i = 0; i < n; i++)cin >> a[i];
    for (int i = 0; i < n; i++) {//初始化两个dp 在上述存入该节点值的情况下就不用再赋值
        dp1[i] = a[i];
        dp2[i] = a[i];
    }
    for (int i = 1; i < n; i++) {
        if (a[i] == 0) {//0乘任何数为0
            dp1[i] = 0;
            dp2[i] = 0;
        }
        if (dp1[i - 1]*a[i] > 0 || dp2[i - 1]*a[i] > 0) {//看看当前节点乘前一个节点的dp1和dp2是否有正数，有则考虑dp1【i】的值发生变化
            tmpup = max(dp1[i - 1] * a[i], dp2[i - 1] * a[i]);//找出i结尾的最大正数积
            dp1[i] = max(a[i], tmpup);//看看这个积和该节点的值那个大
        }
        if (dp1[i - 1]*a[i] < 0 || dp2[i - 1]*a[i] < 0) {
            tmpdown = min(dp1[i - 1] * a[i], dp2[i - 1] * a[i]);
            dp2[i] = min(a[i], tmpdown);//类似地找出i结尾的绝对值最大负数积
        }

    }
    int maxn = a[0];
    for (int i = 0; i < n; i++)maxn = max(maxn, dp1[i]);
    cout << maxn << endl;

}
 /*暴力解能解一半
 for(int i=0;i<n;i++)//j-i的乘积
 for(int j=0;j<i;j++){
    int tmp=1;
    for(int k=j;k<=i;k++)tmp=tmp*a[k];
    dp[i][j]=tmp;
 }
 int maxn=0;
 for(int i=0;i<n;i++)//j-i的乘积
 for(int j=0;j<n;j++)maxn=max(maxn,dp[i][j]);

   cout<<maxn<<endl;*/