唐山网站建设公司哪家好,怎么注册网络域名,互联网制作网站,产品备案号查询平台官网最大子段和
题目描述
给出一个长度为 n n n 的序列 a a a#xff0c;选出其中连续且非空的一段使得这段和最大。
输入格式
第一行是一个整数#xff0c;表示序列的长度 n n n。
第二行有 n n n 个整数#xff0c;第 i i i 个整数表示序列的第 i i i 个数字 a i …最大子段和
题目描述
给出一个长度为 n n n 的序列 a a a选出其中连续且非空的一段使得这段和最大。
输入格式
第一行是一个整数表示序列的长度 n n n。
第二行有 n n n 个整数第 i i i 个整数表示序列的第 i i i 个数字 a i a_i ai。
输出格式
输出一行一个整数表示答案。
样例 #1
样例输入 #1
7
2 -4 3 -1 2 -4 3样例输出 #1
4提示
样例 1 解释
选取 [ 3 , 5 ] [3, 5] [3,5] 子段 { 3 , − 1 , 2 } \{3, -1, 2\} {3,−1,2}其和为 4 4 4。
数据规模与约定
对于 40 % 40\% 40% 的数据保证 n ≤ 2 × 1 0 3 n \leq 2 \times 10^3 n≤2×103。对于 100 % 100\% 100% 的数据保证 1 ≤ n ≤ 2 × 1 0 5 1 \leq n \leq 2 \times 10^5 1≤n≤2×105 − 1 0 4 ≤ a i ≤ 1 0 4 -10^4 \leq a_i \leq 10^4 −104≤ai≤104。 思路
在遍历数组a时累加每个元素的值并在每次更新ans时使用max函数选择当前最大的子段和。
同时如果当前的子段和sum小于0则说明当前的子段对后面的结果没有贡献因此将sum重置为0从下一个元素重新开始计算。 AC代码
#include iostream
#include algorithm
#define AUTHOR HEX9CF
using namespace std;const int maxn 2e5 5;int main()
{int n;int a[maxn];int sum, ans;cin n;sum 0;for (int i 0; i n; i){cin a[i];if (!i){ans a[0];}sum a[i];ans max(ans, sum);if (sum 0){sum 0;}}cout ans endl;return 0;
}
