题解 | #连续子数组的最大乘积#
连续子数组的最大乘积
https://www.nowcoder.com/practice/fd8c819c07c9493887bfac8549c119f4
#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));
}
