动态规划（最长递增子序列）---最长递增子序列

最长递增子序列

300. Longest Increasing Subsequence (Medium)

题目描述：

给定一个数组，找到它的最长递增子序列

思路分析：

动态规划思想，定义一个数组 dp 存储最长递增子序列的长度，dp[n] 表示以 Sn 结尾的序列的最长递增子序列长度。对于一个递增子序列 {Si1, Si2,...,Sim}，如果 im < n 并且 Sim < Sn，此时 {Si1, Si2,..., Sim, Sn} 为一个递增子序列，递增子序列的长度增加 1。满足上述条件的递增子序列中，长度最长的那个递增子序列就是要找的，在长度最长的递增子序列上加上 Sn 就构成了以 Sn 为结尾的最长递增子序列。因此 dp[n] = max{ dp[i]+1 | Si < Sn && i < n} 。

代码：

public int lengthOfLIS(int []nums){if(nums==null||nums.length==0)return 0;int []dp=new int [nums.length];for(int i=0;i<nums.length;i++){int max=1;for(int j=0;j<i;j++){if(nums[i]>nums[j]){max=Math.max(max,dp[j]+1);}}dp[i]=max;}int res=dp[0];for(int i=1;i<nums.length;i++){if(dp[i]>res)res=dp[i];}return res;}