关键字: 动态规划、最大连续子序列和
题目描述:本题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;
}