上升或连续最长子序列问题

朱雀 2023-06-18 05:57 125阅读 0赞

## 最长上升子序列 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70]

我们用

dp[i] 表示数组中索引为 i 结尾的子数组的最长上升子序列的长度

那么我们要求整体最长子序列就是

dp[nums.length - 1]

分析子问题

dp[nums.length - 1]的子问题就是dp[nums.length - 2]，以此类推

分析状态转移，怎么由子问题推导得到原问题的最优解

题目意思就是要我们求得最长上升子序列的长度，对于子序列跟子数组的不同之处就在于，子序列可以跳过，元素和元素在数组中不一定是连续排列的，比如

[2,5,3,7,101]是子序列
    [10,101]也是子序列

题目让我们求最长的一个上升子序列的长度

我们先遍历所有子数组

for(int i = 0;i < nums.length;i++){
        
        for(int j = 0;j < i;j++){
        
            //以上表达的是区间[j,i]的子数组
        }
    }

条件，上升

对于子问题如何能得到原问题

这就涉及到如何判断上升这个条件了，显然，这个很简单

nums[i] > nums[j]  
        nums[i] 可以接在 nums[j]之后（此题要求严格递增），此情况下最长上升子序列长度为 dp[j]+1
        
    nums[i] <= nums[j]
        nums[i] 无法接在 nums[j] 之后，此情况上升子序列不成立，跳过。

所以：

public int lengthOfLIS(int[] nums) {
        
            int len = nums.length;
            if(len == 0){
        
                return 0;
            }
            int[] dp = new int[len];
            int maxLen = 1;
            for(int i = 0;i < len;i++){
        
                int tempLen = 1;
                for(int j = 0;j < i;j++){
        
                    if(nums[i] > nums[j]){
        
                        tempLen = Math.max(dp[j] + 1,tempLen);
                    }
                }
                //记录以索引i结尾的子数组的最长上升子序列长度
                dp[i] = tempLen;
                //记录此时的全局最优解
                if(tempLen > maxLen){
        
                    maxLen = tempLen;
                }
            }
            return maxLen;
        }

## 最长连续递增序列 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 1]

这道题和上面的最长上升子序列的区别在于，这道题要求的连续上升，即

temp = 1;//记录长度
    if nums[i] > nums[i - 1]
    	temp++	//只有连续递增长度才会增加
    else
        temp = 1; //否则只能回到初始值，下一次循环

解答：

/**
         * 最长连续连续递增序列
         * @param nums
         * @return
         */
        public int findLengthOfLCIS(int[] nums) {
        
            int max = 1;
            int temp = 1;
            for(int i = 1;i < nums.length;i++){
        
                if(nums[i] > nums[i - 1]){
        
                    temp++;
                    max = Math.max(max,temp);
                }else{
        
                    temp = 1;
                }
            }
            return max;
        }

## 最长递增子序列的个数 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 2]

这道题目和最长上升子序列问题很相似，但是这道题目要求记录最长上升子序列的组合模式

比如：

[1,3,5,4,7]中[1,3,5,7]和[1,3,4,7]都是最长的上升子序列，长度都为4，但是有两种组合模式

难点就在于记录组合数

所以我们用多一个dp数组来记录这个组合数

combination[i]：表示以索引i结尾的子数组的最大的最大上升子序列的组合数

combination\[i\]初始化都赋值为1，只要有数字，那么至少都是1。

分析状态转移：区间是\[ i，j \]

if nums[i] <= nums[j]:
    	不是上升序列，直接跳过
    else //nums[i] > nums[j]
        if dp[j] + 1 == dp[j]
            //则找到了长度和之前一样的上升子序列
            combination[i] += combination[j]//更新以i结尾的组合数
        else if  dp[j] + 1 > dp[j] 
            //找到了更长的上升序列
            dp[i] = dp[j] + 1//更新长度
            combination[i] = combination[j];//更新以i结尾的组合数

> 参考图：https://leetcode-cn.com/problems/longest-consecutive-sequence/solution/tao-lu-jie-jue-zui-chang-zi-xu-lie-deng-yi-lei-wen/

![dbf04caf16370077061aead090c28d8.jpg][]

/**
         * 最长递增子序列数
         * @param nums
         * @return
         */
        public int findNumberOfLIS(int[] nums) {
        
    
            if (nums.length == 0) {
        
                return 0;
            }
            int[] dp = new int[nums.length];
            int[] combination = new int[nums.length];
            Arrays.fill(dp, 1);
            Arrays.fill(combination, 1);
            int max = 1, res = 0;
            for (int i = 1; i < dp.length; i++) {
        
                for (int j = 0; j < i; j++) {
        
                    if (nums[i] > nums[j]) {
        
                        if (dp[j] + 1 > dp[i]) {
        
                            //找到了更长的上升序列
                            dp[i] = dp[j] + 1;  //更新dp[i]长度
                            combination[i] = combination[j];//更新以i结尾的组合数
                        } else if (dp[j] + 1 == dp[i]) {
        
                            //找到了和之前存的最长序列长度一样的序列
                            combination[i] += combination[j];//更新组合数
                        }
                    }
                }
                max = Math.max(max, dp[i]);
            }
            //统计长度为最长上升序列长度的子序列组合数
            for (int i = 0; i < nums.length; i++){
        
                if (dp[i] == max){
        
                    res += combination[i];
                }
            }
            return res;
        }

## 最长连续序列 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 3]

最长连续序列和最长连续递增序列相似，但是这道题元素和元素之间要求连续，即 1 ，2 ，3 ，4…

思路也和最长连续递增序列相似：

temp = 1;//记录长度
    if nums[i] > nums[i - 1] + 1
    	temp++	//只有连续递增长度才会增加
    else
        temp = 1; //否则只能回到初始值，下一次循环

最长连续递增序列思路：

temp = 1;//记录长度
    if nums[i] > nums[i - 1]
    	temp++	//只有连续递增长度才会增加
    else
        temp = 1; //否则只能回到初始值，下一次循环

实现

public int longestConsecutive1(int[] nums) {
        
            if(nums.length == 0){
        
                return 0;
            }
            int currentMax = 1;
            int max = 0;
            Arrays.sort(nums);
            for(int i = 1;i < nums.length;i++){
        
                if(nums[i] != nums[i - 1]){
        
                    if(nums[i] == nums[i - 1] + 1){
        
                        currentMax++;
                    }else{
        
                        max = Math.max(max,currentMax);
                        currentMax = 1;
                    }
                }
            }
            return Math.max(currentMax,max);
        }

## 最长和谐子序列 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 4]

这道题目先统计所有元素的出现次数

//统计各个元素出现次数
            for(int i : nums){
        
                map.put(i,map.getOrDefault(i,0) + 1);
            }

再遍历一次数组，以当前遍历到的元素为最小值，那么最大值则是 i+1，判断map中是否存在该元素，有则计算最大值和最小值的数量

/**
         * 最长和谐子序列
         * @param nums
         * @return
         */
        public int findLHS(int[] nums) {
        
            if(nums.length == 0){
        
                return 0;
            }
            Map<Integer,Integer> map = new HashMap<>();
            //统计各个元素出现次数
            for(int i : nums){
        
                map.put(i,map.getOrDefault(i,0) + 1);
            }
            int max = 1;
            int temp = 1;
            for(int i : nums){
        
                //以当前遍历元素为最小值，那么最大值则为i + 1，判断map中是否有该元素
                if(map.containsKey(i + 1)){
        
                    temp = map.get(i) + map.get(i + 1);
                    max = Math.max(temp,max);
                }
            }
            return max;
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191127231310175.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191130142741593.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/2019113014423814.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[dbf04caf16370077061aead090c28d8.jpg]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9waWMubGVldGNvZGUtY24uY29tLzEyZmIxMTg4MDQwYWUzYWMzODM3N2E2ZGUxMmQ1NDM1ZWY3M2U5MjEwMmJlYmY4NGYzZDU4OWUzZDYxMjUzYTgtZGJmMDRjYWYxNjM3MDA3NzA2MWFlYWQwOTBjMjhkOC5qcGc?x-oss-process=image/format,png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20191130144530503.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20191130150420760.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkyMjI4OQ==,size_16,color_FFFFFF,t_70