1917: 【例】【基础】最大部分和（连续部分和）
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：8
解决：7
题目描述
有 个整数（），排成一排，例如：
： （个整数）。
其中取连续数（至少选 个）的最大部分和为 （即 ）。
输入
第一行一个整数 。
第二行 个整数 （）。
第二行的数之间有一个空格。
输出
一个整数（即最大的连续的部分和）。
样例输入 复制
7
-2 13 12 9 14 -10 2 样例输出 复制
48提示
#include<bits/stdc++.h>
using namespace std;
/*思路一:穷举实现循环次数:
n+n-1+n-2+...+1
n*(n+1)/2
*/
int a[110], n, i, j;
int ma, s; //ma存放连续最大和，s存放从每个数开始连续数和
int main() {
cin >> n;
for (i = 1; i <= n; i++) {
cin >> a[i];
}
//求从每个数开始连续数的和
for (i = 1; i <= n; i++) {
s = 0;
for (j = i; j <= n; j++) {
s = s + a[j];
ma = max(ma, s);
}
}
cout << ma;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int a[110],dp[110],n,i,j;
int ma;
int main(){
cin >> n;
for (i = 1;i <= n;i++) {
cin >> a[i];
}
dp[1] = a[1];
ma = dp[1];
for (i = 2; i <= n;i++) {
dp[i] = max (dp[i-1]+a[i],a[i]);
ma = max (dp[i],ma);
}
cout << ma;
return 0;
}