题解：洛谷 最大子段乘积

【题目来源】

最大子段乘积

【题目描述】

给出一个数列，要求找出两个不相邻的非空子段，使得两个子段和的乘积最大。

例如对数列 \(2,3,1,9,−2,3\)，可取子段 \(2,3\) 和 \(9,−2,3\)，两段的和分别是 \(2+3=5\) 和 \(9+(−2)+3=10\)，乘积为 \(50\)。

【输入】

第 \(1\) 行，\(1\) 个正整数 \(n\)

第 \(2\) 行，\(n\) 个整数 \(a_1,a_2,⋯ ,a_n\)

【输出】

输出最大的乘积。

【输入样例】

6
2 3 1 9 -2 3

【输出样例】

50

【代码详解】

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5 + 5;
int n, a[N], s1[N], s2[N], f1[N], f2[N], g1[N], g2[N];
long long ans = -1e18;  // 答案初始化为负无穷int main()
{cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];}// 从前向后计算for (int i = 1; i <= n; i++){s1[i] = max(a[i], s1[i - 1] + a[i]);  // 最大连续子段和s2[i] = min(a[i], s2[i - 1] + a[i]);  // 最小连续子段和}// 初始化memset(f1, -0x3f, sizeof(f1));memset(g1, -0x3f, sizeof(g1));memset(f2, 0x3f, sizeof(f2));memset(g2, 0x3f, sizeof(g2));// 前缀最大值/最小值for (int i = 1; i <= n; i++){f1[i] = max(f1[i - 1], s1[i]);  // 前缀最大子段和f2[i] = min(f2[i - 1], s2[i]);  // 前缀最小子段和}// 从后向前计算for (int i = n; i >= 1; i--){s1[i] = max(a[i], s1[i + 1] + a[i]);  // 后缀最大子段和s2[i] = min(a[i], s2[i + 1] + a[i]);  // 后缀最小子段和}// 后缀最大值/最小值for (int i = 1; i <= n; i++){g1[i] = max(g1[i + 1], s1[i]);  // 后缀最大子段和g2[i] = min(g2[i + 1], s2[i]);  // 后缀最小子段和}// 枚举分割点ifor (int i = 2; i < n; i++){ans = max(ans, 1ll * f1[i - 1] * g1[i + 1]);  // 最大×最大ans = max(ans, 1ll * f2[i - 1] * g2[i + 1]);  // 最小×最小}cout << ans;return 0;
}

【运行结果】

6
2 3 1 9 -2 3
50