题目描述：题目链接
给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入:[10,9,2,5,3,7,101,18]输出: 4
解释: 最长的上升子序列是[2,3,7,101]，它的长度是4。
说明:
- 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
- 你算法的时间复杂度应该为 O(n2) 。
进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
这个题目和最长公共子序列一样，都是可以利用动态规划来解决问题的：
可以利用常见的动态规划思路：
1：将问题归纳。可以定义 dp[ i ] 来表示前 i 个字符中的最长的公共子序列。
2：给出动态规划的递推思路。dp[ i ] = max { dp[ j ] + 1} (0 <= j < i ,nums[j] < nums[i] )
3：初始化。这一步最重要，因为一个数字的时候最长上升子序列为1，所以我们需要将初始化数组为1
其实只要我们细心的推理，可以很容易的得到递推关系式。
下面给出具体的代码描述：
class Solution {
public int lengthOfLIS(int[] nums) {
//如果数组为空，或者数组长度为0，则直接返回0
if(nums == null || nums.length == 0){
return 0;
}
int len = nums.length;
int[] a = new int[len];
Arrays.fill(a,1);
//利用两层for循环来处理
for(int i = 1; i < len; i++){
for(int j = 0; j < i; j++){
if(nums[j] < nums[i]){
a[i] = Math.max(a[i],a[j]+1);
}
}
}
int max = 1;
for(int i = 0; i < len; i++){
if(a[i] > max){
max = a[i];
}
}
return max;
}
}