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

import sys

# 6:13 

# dp[i][j]为子数组i~j的乘积，dp[i][j]=dp[i][j-1]*nums[j]
# 直接用超内存，其实因为dp[i][j]的更新和i没关系，就可以改为1维的dp[j]为当前i到j的值
# 最后发现还是运行超时,检查剪枝策略
# (1) 当当前max_v>0并且nums[i-1]>0的时候，这个分枝可以剪掉，因为缺少乘一个正整数肯定会使max_v减小
# 还是超时

# 重新考虑问题
# 假设 dp[i]为以i结尾的最大连续子数组乘积
# 讨论形成最大值的情况，最大值为max_v，当下一个num为正数的时候，最大值为max_v * nums[i+1]
# 要么是以i结尾的最大负数，乘当前是负数的最大
# 所以要记录以i结尾的最大值和最小值


# 方法一，超时
# n = int(input())
# nums = list(map(int,input().split()))


# max_v = - (2**32-1)

# for i in range(1,n+1):
#     if max_v > 0 and i-2>=0 and nums[i-2]>0:continue
#     dp = [0]*(n+1)
#     for j in range(i,n+1):
#         if i==j:
#             dp[j] = nums[i-1]
#         else:
#             dp[j] = dp[j-1] * nums[j-1]
#         max_v = max(max_v, dp[j])

# print(max_v)

n = int(input())
nums = list(map(int, input().split()))
 
dp_max = [float('-inf')] * n
dp_min = [float('inf')] * n
dp_max[0] = dp_min[0] = nums[0]
for i in range(1, n):
    dp_max[i] = max(dp_max[i-1]*nums[i], dp_min[i-1]*nums[i], nums[i])
    dp_min[i] = min(dp_max[i-1]*nums[i], dp_min[i-1]*nums[i], nums[i])
     
print(max(max(dp_max), max(dp_min)))