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

#include "stdio.h"
//三者求最大值函数
int max(int a , int b , int c){
    if(a >= b && a >= c)return a;
    else if(b >= a && b >= c)return b;
    else if(c >= a && c >= b)return c;
    else return 0;
}
//三者求最小值函数
int min(int a , int b , int c){
    if(a <= b && a <= c)return a;
    else if(b <= a && b <= c)return b;
    else if(c <= a && c <= b)return c;
    else return 0;
}

int func(int arr[], int n){
    int dpMax[n], dpMin[n];//分别维护截止当前元素的最大乘积和最小乘积（考虑到负负得正，应该维护两个值）
    dpMax[0] = dpMin[0] = arr[0];
    for(int i = 1; i < n; i++){
        dpMax[i] = max(dpMax[i-1] * arr[i], dpMin[i-1] * arr[i], arr[i]);//最大值可能是正正得正，最大值×当前值，也可能
        dpMin[i] = min(dpMax[i-1] * arr[i], dpMin[i-1] * arr[i], arr[i]);//负负得正，最小值×当前值，也可能是当前值，三者取最大即可
    }                                                                    //最小值同理
    //遍历最大值数组，找到最大值
    int max = dpMax[0];
    for(int i = 0; i < n; i++){
        if(dpMax[i] > max)max = dpMax[i];
    }
    return max;
}
int main(){
    int n = 0;
    scanf("%d",&n);
    int arr[n];
    for(int i = 0; i < n; i++){
        scanf("%d",&arr[i]);
    }
    printf("%d",func(arr,n));
}