【题目描述】
给出一个数组 \(a_1,a_2,⋯ ,a_n\)，删除一个元素后，求它的最大子段和。（子段是指数组中连续的一段元素）
删除的元素可以由你自由选择，但是不能不删除任何元素，输出你能得到的最大的子段和。
【输入】
第 \(1\) 行，\(1\) 个正整数 \(n\)。
第 \(2\) 行，\(n\) 个整数 \(a_1,a_2,⋯ ,a_n\)。
【输出】
输出能得到的最大的子段和。
【输入样例】
5
9 5 -6 -10 7
【输出样例】
15
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 1005;
int n, a[N]; // n: 数组大小，a: 数组元素
int dp1[N], dp2[N]; // dp1: 从前向后的最大子段和，dp2: 从后向前的最大子段和int main()
{cin >> n; // 读入数组大小bool flag = 0; // 标记是否存在非负数int mx = -1e9; // 记录数组中的最大值for (int i = 1; i <= n; i++){cin >> a[i]; // 读入数组元素if (a[i] >= 0) // 如果存在非负数{flag = 1;}mx = max(mx, a[i]); // 更新最大值}// 如果所有数都是负数，则最大子段和就是最大的那个负数if (flag == 0){cout << mx << endl;return 0;}// 计算从前向后的最大子段和// dp1[i]表示以a[i]结尾的最大子段和dp1[1] = a[1];for (int i = 2; i <= n; i++){dp1[i] = max(dp1[i - 1] + a[i], a[i]);}// 计算从后向前的最大子段和// dp2[i]表示以a[i]开头的最大子段和dp2[1] = a[n];for (int i = n; i >= 1; i--) // 这里有个小问题，应该是从n-1开始{dp2[i] = max(dp2[i + 1] + a[i], a[i]);}int maxn = -1e9; // 记录最大两段子段和for (int i = 1; i <= n; i++){// 计算不相邻的两段最大子段和// 注意：这里dp1[i-1]和dp2[i+1]分别表示第i个元素左边和右边的最大子段和maxn = max(maxn, dp1[i - 1] + dp2[i + 1]);}cout << maxn << endl; // 输出结果return 0;
}
【运行结果】
5
9 5 -6 -10 7
15