子串和
子串和
描述
给定一整型数列{a1,a2...,an}，找出连续非空子串{ax,ax+1,...,ay}，使得该子序列的和最大，其中，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 <string>
#include <stack>
#include <set>
#include <memory.h>
#include <map>
#include <iomanip>
#include <queue>
#include <algorithm>
#define max(a,b) (a>b ? a:b)
using namespace std;
int dp[1000001];
int arr[1000001];
int main()
{
int n;
int t;
cin >> t;
while (t--)
{
cin >> n;
int flag = 0;
int M = -99999999;
for (int i = 0; i < n; i++)
{
cin >> arr[i];
if (arr[i]>0)
flag = 1;
if (arr[i] > M)
M = arr[i];
}
if (flag == 0)
{
cout << M << endl;
continue;
}
memset(dp, 0, sizeof(dp));
dp[0] = arr[0];
int Max = -9999999;
for (int i = 1; i < n; i++)
{
if (dp[i - 1] >= 0)
dp[i] = dp[i - 1] + arr[i];
else
dp[i] = arr[i];
if (dp[i]>Max)
Max = dp[i];
}
cout << Max<< endl;
}
return 0;
} 本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2014-11-02 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录