本文主要是介绍最大子段和问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
最大子段和问题
分数 15
全屏浏览
切换布局
作者 王东
单位 贵州师范学院
最大子段和问题。给定由n个整数组成的序列,求序列中子段的最大和,若所有整数均为负整数时定义最大子段和为0。
输入格式:
第一行输入整数个数n(1≤n≤1000),再依次输入n个整数。
输出格式:
输出最大子段和。
输入样例1:
5
-2 11 -4 13 -5 -2
输出样例1:
20
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
#include <bits/stdc++.h>
using namespace std;
int main(){int n;cin>>n;int s[n+1];for(int i=1;i<=n;i++){cin>>s[i];}int sum=0;int besti=0,bestj=0;for(int i=1;i<=n;i++){int tempsum=0;for(int j=i;j<=n;j++){tempsum+=s[j];if(tempsum>sum){sum=tempsum;besti = i;bestj = j;}}}cout<<sum;return 0;
}
这篇关于最大子段和问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!