建筑网站主页,WordPress小工具吗美化,个人域名可以做公司网站么,可以免费建手机网站P1115 最大子段和 题目描述 给出一段序列#xff0c;选出其中连续且非空的一段使得这段和最大。 输入输出格式 输入格式#xff1a; 输入文件maxsum1.in的第一行是一个正整数N#xff0c;表示了序列的长度。 第2行包含N个绝对值不大于10000的整数A[i]#xff0c;描述了这段… P1115 最大子段和 题目描述 给出一段序列选出其中连续且非空的一段使得这段和最大。 输入输出格式 输入格式 输入文件maxsum1.in的第一行是一个正整数N表示了序列的长度。 第2行包含N个绝对值不大于10000的整数A[i]描述了这段序列。 输出格式 输入文件maxsum1.out仅包括1个整数为最大的子段和是多少。子段的最小长度为1。 输入输出样例 输入样例#1 7
2 -4 3 -1 2 -4 3 输出样例#1 4 说明 【样例说明】2 -4 3 -1 2 -4 3 【数据规模与约定】 对于40%的数据有N ≤ 2000。 对于100%的数据有N ≤ 200000。 可以看出来是一道dp题转移方程很好找 f[i] max(f[i-1], 0) a[i] 边界条件是f[0] 0 为什么要和0作比较因为如果比0小那么这个字段和活着也是挺失败的不如重修2333 AC①: dp(48ms) 1 #include cstdio2 #include algorithm3 4 int a[200005];5 int f[200005];6 7 int main()8 {9 int n;
10 scanf(%d, n);
11 for(int i1; in; i)
12 scanf(%d, a[i]);
13
14 for(int i1; in; i)
15 f[i] std::max(f[i-1], 0) a[i];
16
17 int maxx -1234567;
18 for(int i1; in; i)
19 if(f[i] maxx)
20 maxx f[i];
21
22 printf(%d, maxx);
23 return 0;
24 } 还可以用贪心的思路做 AC②: (贪心 36ms) 1 #include cstdio2 3 int main()4 {5 int n, a, b, maxx;6 scanf(%d, n);7 b maxx -1234567; // b表示前几个字段和最大值8 for(int i1; in; i)9 {
10 scanf(%d, a);
11 if(b 0) b a; // 如果b0 那么不如直接重开
12 else b a; // b0 说明前面的字段和比较大 可以继续加下去
13 if(b maxx) maxx b;
14 }
15 printf(%d, maxx);
16 return 0;
17 } 转载于:https://www.cnblogs.com/yBaka/p/7397260.html
