继续进行动态规划练习。

题目如下:

问题描述

一个数的序列ai, 当a1 < a2 < a3… < aS的时候,我们称这个序列是上升的。对于给定的一个序列(a,a2, …,aN), 我们可以得到一些上升的子序列(ai1,ai2, ..,aiK) ,这 里1 <=i1 < i2 <… < iK<=N。

比如,对于序列(1,7,3,5,9,4,8),有它的一些上升子序列,如(1,7),(3,4,8)等等。这些子序列中最长的长度是4,比如子序列(1,3,5,8)

对于给定的序列,求出最长上升子序列的长度。

输入要求:

  • 第一行,一个数字n

  • 第二行,n个数字用空格分隔

输出要求:

  • 一个数字,表示最长上升子序列长度

数据范围:1 < n <=1000

范例输入:

1
2
14
13 7 9 16 38 24 37 18 44 19 21 22 63 15

范例输出:

1
8

题解如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX 1005
int a[MAX]; //存放数组
int maxLen[MAX];//存放以对应元素为终点的最长上升子序列长度
int main(void) {
int n;
cin >> n;
for(int i = 1;i <= n; i++){
cin>>a[i];
maxLen[i] = 1; // init: max==1
//每个元素的最长上升子序列数都至少为1(即自身)
}
for(int i=2;i <= n;i++){
/*
每次计算a[i]处的最长上升子序列长度
从i=2处开始,前置数据可用于后续递推
*/
for(int j = 1;j < i;j++){
if(a[i] > a[j])
maxLen[i] = max(maxLen[i],maxLen[j]+1);
//以maxLen[j]+1为依据,更新该位置最长子序列长度
}
}
cout<< *max_element(maxLen+1,maxLen+n+1); //Prints:8
return 0;
}

时间复杂度为O(N^2)