（2019复旦机试）最大连续子序列

关键字： 动态规划、最大连续子序列和

题目描述：本题OJ链接

给定一个数字序列A1,A2…An，求i,j(1<=i<=j<=n)，使得Ai+…+Aj最大，输出这个最大和。

输入输出格式

输入描述:

第一行输入一个整数n，表示数列大小 第二行输入n个整数

输出描述:

输出一个整数，求i,j(1<=i<=j<=n)，使得Ai+…+Aj最大

思路分析：

最大连续子序列和问题 dp[i] = max(dp[i-1]+nums[i], nums[i]) //dp[i]即为i位置能达到的最大的连续子序列和

代码：

#include<iostream>
#include<vector>
using namespace std;
/*
输入案例
6
-2 11 -4 13 -5 -2
*/
int main() {
	int n;
	cin >> n;
	vector<int> nums(n);
	for (int i = 0; i < n; i++) {
		cin >> nums[i];
	}
	vector<int> dp(n, 0);
	dp[0] = nums[0];
	int res = dp[0];
	for (int i = 1; i < n; i++) {
		dp[i] = max(dp[i - 1] + nums[i], nums[i]);
		res = max(res, dp[i]);
	} 
	cout << res << endl;
}