给定一个序列
a1, a2, a3, ...., aN
找出其中的递增的最长子序列
基本思想：DP的方法，对数字 ai 来说，假设前(1,2,....,i-1)个数字中的最长子序列长度为m，如果 ai 比这个子序列中的最大的一个数大，则 ai 加入到这个最长子序列，否则 goto a(i+1)，代码如下
1
# include <iostream>
2# include <vector>
3# include <algorithm>
4
int main() 
{
5
6 int length = 8;
7
int number[] = {1,-1,2,-3,4,-5,6,-7};
8
9 std::vector<int> Lis(length);
10
11 for (int i = 0; i < length; i++) {
12 Lis[i] = 1;
13 for (int j = 0; j < i; j++) {
14 if (number[j] < number[i] && Lis[j] + 1 > Lis[i]) {
15 Lis[i] = Lis[j] + 1;
16
}
17 }
18 }
19
20 std::cout<<*max_element(Lis.begin(), Lis.end())<<std::endl;
21
22 return 0;
23
}