题目的链接在这里:https://leetcode-cn.com/problems/longest-increasing-subsequence/
子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
代码如下:
class Solution { //这个最长子序列的问题就是 //先判断这个i是不是大于 相对的最大值 然后是的话 就需要判断是加入还是不加入 好像是这个说法吧 有点像01背包 //假设i 不满足 那dp[i]的最大值就是记录的最大值 如果i满足大于最大的那个的话 就最大值加一 然后那个最大是dp[i]吧 这样应该就行了 public int lengthOfLIS(int[] nums) { //用来记录最长递增子序列的长度 int max=1; //用来记录最大值 int max_value=nums[0]; int n=nums.length; //从0-n-1 int dp[]=new int[n]; /* //然后开始初始化 //意思就是 只有一个的时候 长度是1 dp[0]=1; //从1 也就是第二个开始 max=1; max_value=nums[0];*/ for(int i=0;i<n;i++){ dp[i]=1; } //然后是统计最大的 那就直接在循环里找最大的吧 for(int i=1;i<n;i++){ //开始递归判断 可是好像存在不是从1开始的呢。。。如果第一个是很大的一个数组9 1 2这样呢 //所以应该是这样 从后往前找 第一个小于dp的数 找到了就dp[i]=dp[k]+1 如果是等于的话 就直接赋值dp[i]=dp[k] //如果没找到 就存1 要不就是赋初值全是1 所以其他情况就忽略了 //那就再优化一下 在这个的基础之上 先去判断不行的 甚至从后往前判断也是不行的 //所以就是 要找到当前这个值 之前的那些里的最大小于自己的值 其实可以做一个排序 但是排序的话就会把对应的数值给 //忘掉 int temp_max=1; for(int k=i-1;k>=0;k--){ //从后往前 不然的话 这个遍历就是找到最大但是小于当前值的那个数 但是实现不了 //那就是 在这里进行暴力统计 就是if不break了 所以就找比他小的 然后统计每一个的值 找到那个最大的值 if(nums[i]>nums[k]){ //不是找到第一个 而是找到所有比他小的 然后统计最小值 int temp=dp[k]+1; //然后也不break了 知道找到最大的那个 if(temp>temp_max) temp_max=temp; } if(nums[i]==nums[k]){ //也是找所有的 等于的话就不加一了 int temp=dp[k]; //然后也不break了 知道找到最大的那个 if(temp>temp_max) temp_max=temp; } } dp[i]=temp_max; if(dp[i]>max) max=dp[i]; } //结果还是需要用我以前的老方子 直接判断当前的i的值是不是大于记录的最大值 如果是的话就这个更新并且记录一下 /* for(int i=1;i<n;i++){ //那都不需要用到dp了呀 if(nums[i]>max_value){ //如果这个更大的话 就进行记录 max_value=nums[i]; max++; } }*/ return max; } }