【题目描述】
皮皮刚刚学完最大子段和，老师为了检测皮皮是否真正掌握，决定对它进行提问。
给出数组 \(a\) 的元素 \(a[1],a[2],⋯ ,a[n]\) 的值，给定一个 \(1\) ~ \(n\) 之间的位置 \(pos\)，请问 \(a[pos]\)~\(a[n]\) 之间的最大子段和是多少？请回答 \(m\) 个这样的问题。
【输入】
第 \(1\) 行，是两个正整数 \(n\) 和 \(m\)，分别表示数组 \(a\) 的长度和询问的次数。
第 \(2\) 行，用空格隔开的 \(n\) 个整数，依次是 \(a[1],a[2],⋯ ,a[n]\) 的值。
接下来的 \(m\) 行，每行一个正整数 \(pos\)，表示询问的位置。
【输出】
共 \(m\) 行，每行一个整数，为所求的最大子段和.
【输入样例】
6 1
1 -6 5 -4 2 4
6
【输出样例】
4
【代码详解】
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;#define int long long
const int N = 100005;
int n, a[N], dp[N], pos, maxn = -1e9, m; // n: 数组长度，a: 数组元素，dp: 动态规划数组，pos: 查询位置，m: 查询次数signed main()
{cin >> n >> m; // 读入数组长度和查询次数for (int i = 1; i <= n; i++){cin >> a[i]; // 读入数组元素}// 从后向前计算最大子段和// dp[i]表示以a[i]开头的最大子段和for (int i = n; i >= 1; i--){dp[i] = max(dp[i + 1] + a[i], a[i]); // 要么从当前位置开始，要么加上后面的}// 从后向前处理，dp[i]表示从i到n的最大子段和for (int i = n - 1; i >= 1; i--){dp[i] = max(dp[i + 1], dp[i]); // 更新为从i到n的最大子段和}// 调试输出// for (int i=1;i<=n;i++)// cout<<dp[i]<<' ';// cout<<endl;// 处理查询while (m--){cin >> pos; // 读入查询位置cout << dp[pos] << endl; // 输出从pos位置开始到结尾的最大子段和}return 0;
}
【运行结果】
6 1
1 -6 5 -4 2 4
6
4