题目，给定数字序列A，求A中最长的递增序列。
O(n^2)算法思想： 序列A的长度为n，先求以A[j]结尾的最长递增序列L[j]，最终的解肯定在L[j]中（最长递增序列的结尾元素肯定为序列A的某个元素）。（其中1<=j<=n）
**第归关系**：以A[j]结尾的最长递增序列L[j] = max{A[i]}+1,其中 i < j，A[i] < a[j]。
即求以A[j]结尾的最长递增序列L[j] 就相当于求 在序列A中，以排在A[j]前的元素每个元素结尾的最长递增序列，加上A[j]后仍然为递增序列。
要以A[j]结尾：
- 最长递增子序列中每个元素一定小于A[j]；
- 每个元素的下表必定小于j
O(n^2)算法代码：
#include <iostream>
using namespace std;
void lis(int a[], int n){
int l[n];
int max = 0;
for (int j = 0; j < n; j++){
l[j] = 0;
}
l[0]=1;
for (int j = 1; j < n; j++){
for (int i = 0; i < j; i++){
if(a[i] < a[j]){
int tmp = l[i] + 1;
if(tmp > l[j]){
l[j] = tmp;
}
}
}
if(max < l[j]){
max = l[j];
}
}
cout << max << endl;
}
int main() {
int a[] ={5, 6, 7, 1, 2, 8};
lis(a, 6);
return 0;
}
