最长上升子序列

1.问题描述

一个数的序列bi，当b1 < b2 < ... < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, 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).
你的任务，就是对于给定的序列，求出最长上升子序列的长度。

2.解题思路

• 考虑穷举的话，算法复杂度为2^n，不可能使用穷举。
• 那么从动态规划考虑，那么阶段的划分是十分明显的：按序列的下标来分。
• 假设f(i)是以i结尾的最长上升序列的长度，思考这个递推公式：f(i) = max [ f(j) + 1 ] 0 <= j < i
• 上面的公式明显不完整，我们还要考虑上升这个要求。
• 那么递推公式为：f(i) = max{ [ f(j) + 1 ] * [ b(j) < b(i) ] * [ 0 <= j < i ] } 这里的<、<=为逻辑运算符

3.代码

实现
cpp
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int s[100];
int f[100];
int main()
{
int n;
cin >> n;
for(int i = 0; i < n; i ++)
{
cin >> s[i];
}
f[0] = 1;
for(int i = 1; i < n; i ++)
{
int tt = 0;
for(int j = i - 1; j >= 0; j --)
{
if(s[i] > s[j])
{
if(f[j] > tt)
{
tt = f[j];
}
}
}
f[i] = tt + 1;
}
int ans = 0;
for(int i = 0; i < n; i ++)
{
if(f[i] > ans)
{
ans = f[i];
}
}
cout << ans;
}

3.总结
算法复杂度：O(n^2)

作者：@StevenShang
Emai：cocbbszx@163.com

真正危险的不是计算机开始像人那样去思考，而是人类开始像计算机一样思考。——西德尼·哈里斯