• • 题目描述
    • • 输入格式
      • 输出格式
      • 数据范围
      • 输入样例1：
      • 输出样例1：
      • 输入样例2：
      • 输出样例2：
      • 输入样例3：
      • 输出样例3：
  • 简单动态规划
    • 分析
    • 代码
    • 时间复杂度
  • 参考文章

题目传送门

题目描述

给出一个整数序列 SS，其中有 NN 个数，定义其中一个非空连续子序列 TT 中所有数的和为 TT 的“序列和”。

对于 SS 的所有非空连续子序列 TT，求最大的序列和。

输入格式

第一行包含一个整数 NN。

第二行包含 NN 个整数，表示序列中的元素。

输出格式

输出一个数，表示最大序列和。

数据范围

1≤N≤1061≤N≤106,
序列中的元素的取值范围 [?109,109][?109,109]。

输入样例1：

5
1 5 -3 2 4

输出样例1：

9

输入样例2：

6
1 -2 3 4 -10 6

输出样例2：

7

输入样例3：

4
-3 -1 -2 -5

输出样例3：

-1

简单动态规划

分析

说实话这个题我还是不太理解为什么这么解决

用dp[i]表示以a[i]为结尾的最大连续非空子序列的值

代码

#include
#include
using namespace std;
typedef long long LL;
const int N = 1e6 + 10; 
LL dp[N]; // dp[i]表示以i为结尾的前i个数中非空连续子序列最大和 
int n;
int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
	{
		int a;
		scanf("%d", &a);
		if(dp[i-1] + a < a) dp[i] = a;
		else 				dp[i] = dp[i-1] + a;
	}
	LL res = -0x3f3f3f3f; 
	for(int i = 1; i <= n; i++) res = max(res, dp[i]);
	
	printf("%lld\n", res);
	return 0;	
} 

时间复杂度

参考文章