FDU 2019 | 2. 最大连续子序列

本文主要是介绍FDU 2019 | 2. 最大连续子序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 题目描述

给定一个数字序列A1,A2…An，求i,j(1<=i<=j<=n)，使得Ai+…+Aj最大，输出这个最大和。
第一行输入一个整数n，表示数列大小
第二行输入n个整数
输入样例

6
-2 11 -4 13 -5 -2

输出样例

20

2. 我的尝试

经典动态规划问题

#include <bits/stdc++.h>using namespace std;
const int N = 1e5 + 10, INF = 0x3f3f3f3f;// f[i]表示以下标i元素结尾的最大连续子序列和
int f[N], a[N];
int n;int main()
{int res = - INF;cin >> n;for (int i = 1; i <= n; i ++)scanf("%d", &a[i]);f[1] = a[1];// 必须要以a[i]结尾，那么有俩种情况：// 1. 以a[i-1]结尾的最大连续子序列再接上a[i]// 2. a[i]自己独自作为一个序列// 两者取最大值即可for (int i = 2; i <= n; i++){f[i] = max(a[i], f[i-1] + a[i]);}for (int i = 1; i < n; i++)res = max(res, f[i]);cout << res;return 0;
}

这篇关于FDU 2019 | 2. 最大连续子序列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---