寒假学习-第六专题-动态规划_给出一个长度为 n 的序列 a,选出其中连续且非空的一段使得这段和最大。

1.

Description

给出一个长度为n的序列a，选出其中连续且非空的一段使得这段和最大。

Input

第一行是一个整数，表示序列的长度n。

第二行有n个整数，第i个整数表示序列的第i个数字ai​。

Output

输出一行一个整数表示答案。

Sample 1

72 -4 3 -1 2 -4 3

4

Hint

样例 1 解释

选取[3,5]子段{3,−1,2}，其和为4。

数据规模与约定

• 对于40%的数据，保证n≤2×10^3。
• 对于100%的数据，保证1≤n≤2×10^5，−10^4≤ai≤10^4。

思路：对于该序列假设b为序列中的一个段子序列和对于他的序列中下一个数a若a+b 大于等于b则加上a若a+b 小于 a则 a为新的子序列和 即 b = max（a， a+b）

AC代码：

#include using namespace std;const int N = 2e5 + 1;int a, b, n, ans = -2e9;int main(){cin >> n;for(int i = 1; i > a;if(i == 1) b = a;else b = max(a, a+b);ans = max(ans, b);}cout << ans;return 0;}

2.

Description

给出1,2,…,n的两个排列P1​和P2​，求它们的最长公共子序列。

Input

第一行是一个数n。

接下来两行，每行为n个数，为自然数1,2,…,n的一个排列。

Output

一个数，即最长公共子序列的长度。

Sample 1

5 3 2 1 4 51 2 3 4 5

3