题目要求： 给定一个无序的整数数组，找到其中最长上升子序列的长度 输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4
解题思路： 动态规划，定义一个dp[]数组存储以当前数字结尾的最长上升子序列的长度。在计算 dp[i]之前，我们已经计算出 dp[0…i−1]的值。则状态转移方程为：
dp[i]=max(dp[j])+1,其中0≤j<i且num[j]<num[i]图解： 定义一个dp数组，10为第一个元素所以以10结尾的上升子序列长度为19比10小，所以以9结尾的上升子学列长度也为1 2比在它之前的9或10都小，所以以2结尾的上升子学列长度也为1 因为5比2大，所以以5结尾的上升子学列长度为以2结尾的上升子学列加上其本身长度1：1+1=2 因为3比2大，所以以3结尾的上升子学列长度也为以2结尾的上升子学列加上其本身长度1：1+1=2 全部遍历完玩后可得 代码实现
class Solution { public int lengthOfLIS(int[] nums) { if (nums.length == 0) { return 0; } int maxlen=1;//定义最长上升子序列 int[] db=new int[nums.length];//定义db数组 db[0]=1;//以第一个数字结尾的上升子序列长度必定为1 for(int i=1;i<nums.length;i++){ int maxleni=1;//以当前结尾的最大上升子序列，默认为1（如果当前数字为最小数字） for(int j=0;j<i;j++){//遍历当前数字前所有的数字 if(nums[j]<nums[i]){ if((db[j]+1)>maxleni){maxleni=db[j]+1;}} } db[i]=maxleni;//得到以当前数字结尾的最大上升子序列的长度 maxlen=Math.max(maxlen,db[i]); } return maxlen; } }