子串和
时间限制：
5000 ms | 内存限制：65535 KB
5000 ms | 内存限制：65535 KB
难度：
3
3
- 描述
-
给定一整型数列{a
1,a
2…,a
n}，找出连续非空子串{a
x,a
x+1,…,a
y}，使得该子序列的和最大，其中，1<=x<=y<=n。
- 输入
-
第一行是一个整数N(N<=10)表示测试数据的组数）
每组测试数据的第一行是一个整数n表示序列中共有n个整数，随后的一行里有n个整数I(-100=<I<=100)，表示数列中的所有元素。(0<n<=1000000) - 输出
- 对于每组测试数据输出和最大的连续子串的和。
- 样例输入
-
1 5 1 2 -1 3 -2
- 样例输出
-
5
思路：贪心算法
#include <iostream> #include <cmath> #include <algorithm> #include <cstdio> using namespace std; int main(){ int n; scanf("%d",&n); while (n--) { int m; scanf("%d",&m); int *a = new int [m]; for (int i = 0 ; i < m;i++) { scanf("%d",&a[i]); } //解法1 int ans = a[0]; for (int x = 1; x < m ; x++) { a[x] = max(a[x-1]+a[x],a[x]); ans = max(ans,a[x]); } cout<<ans<<endl; //解法2 /*int big = -100; int sum = 0; for (int k = 0 ; k < m; k++) { sum += a[k]; if (big < sum) { big = sum; }else if (sum<0) { sum = 0; } } cout<<big<<endl;*/ } return 0; }
原创文章，作者：奋斗，如若转载，请注明出处：https://blog.ytso.com/20698.html