找出最长连续递增子序列（部分有序）

待我称王封你为后i 2022-12-11 07:25 115阅读 0赞

#### 题目： ####

给定一个顺序存储的线性表，请设计一个算法查找该线性表中最长的连续递增子序列。例如，\{1,9,2,5,7,3,4,6,8,0\} 中最长的递增子序列为 \{3,4,6,8\} 。

#### 分析： ####

下面是我以前在网上搜的一种写法，挺好理解的。令递增子序列长度 k 为1，如果是递增的，就让k++，反之说明不再是递增的，就让k回到初始的1，为了记住这一段递增序列的长度和开头位置，引入了maxLen 和 begin ，用 maxLen 保存该长度，用 begin 保存开头位置，如果下一个递增子序列的长度＞maxLen，更新 maxLen 和 begin，然后继续下一子序列，直到结束。

#### 代码实现： ####

public class _17找出最长连续递增子序列_部分有序 { 	 
    
    	 public static void getMaxLen(int[] arr) { 
    		int k = 1;
            int maxLen = 1;   
            int begin = 0;
            for (int end = 1; end < arr.length; end++) { 
                if(arr[end-1]<=arr[end]){ 
                    k++;
                } else { 
                    k=1;
                }
                if (k>=maxLen) { 
                    maxLen = k;
                    begin = end-maxLen+1;
                }
            }        
            for(int i = begin;i<begin+maxLen;i++) { 
            	System.out.print(arr[i] + " ");
            }
        }
    
    	public static void main(String[] args) { 
    		 int []arr = { 1,9,2,5,7,3,4,6,8,0};
    		 getMaxLen(arr);
    	 }
    }

#### 运行结果： ####

![在这里插入图片描述][20200929085710278.png_pic_center]

[20200929085710278.png_pic_center]: /images/20221123/77b4d17dd1c24ca1a4f5238391f0babb.png

发表评论取消回复

表情：

评论列表（有 0 条评论，115人围观）

还没有评论，来说两句吧...

相关阅读

相关最长递增子序列

问题给定一个长度为N的数组，找出一个最长的单调自增子序列（不一定连续，但是顺序不能乱）。例如：给定一个长度为6的数组A\{5， 6， 7， 1， 2， 8\}，则其...

曾经终败给现在/ 2024年04月17日 19:33/ 0 赞/ 44 阅读

相关最长递增子序列

300.力扣给你一个整数数组 `nums` ，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如

客官°小女子只卖身不卖艺/ 2024年03月25日 23:05/ 0 赞/ 14 阅读

相关找出最长连续递增子序列（部分有序）

题目：给定一个顺序存储的线性表，请设计一个算法查找该线性表中最长的连续递增子序列。例如，\{1,9,2,5,7,3,4,6,8,0\} 中最长的递增子序列为 \{3

待我称王封你为后i/ 2022年12月11日 07:25/ 0 赞/ 116 阅读

相关最长递增子序列

/ 输入一个无序的整数数组，请你找到其中最长递增子序列的长度最长递增子序列不一定是连续的 / public class LIS {

刺骨的言语ヽ痛彻心扉/ 2022年10月27日 05:21/ 0 赞/ 152 阅读

相关最长递增子序列

最长递增子序列 [http://blog.csdn.net/lisonglisonglisong/article/details/45241965][http_blog.

淡淡的烟草味﹌/ 2022年08月08日 05:08/ 0 赞/ 196 阅读

相关最长递增子序列

给出长度为N的数组，找出这个数组的最长递增子序列。(递增子序列是指，子序列的元素是递增的）例如：5 1 6 8 2 4 5 10，最长递增子序列是1 2 4 5 10。

灰太狼/ 2022年06月12日 11:23/ 0 赞/ 209 阅读

相关求数组中最长连续递增子序列

求子数组的最大和题目描述：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大

蔚落/ 2022年06月09日 07:54/ 0 赞/ 157 阅读

相关找出最长连续子序列

![这里写图片描述][70] import java.util.; public class Solution { //方法一:时间

桃扇骨/ 2022年05月21日 05:17/ 0 赞/ 167 阅读

相关最长递增子序列

最长递增子序列问题的求解最长递增子序列问题是一个很基本、较常见的小问题，但这个问题的求解方法却并不那么显而易见，需要较深入的思考和较好的算法素养才能得出良好的算法。由

桃扇骨/ 2022年04月16日 06:55/ 0 赞/ 199 阅读

相关 674-最长连续递增序列

题目描述给定一个未经排序的整数数组，找到最长且连续的的递增序列。示例 1: 输入: [1,3,5,4,7] 输出: 3 解释: 最长连

布满荆棘的人生/ 2022年01月14日 11:21/ 0 赞/ 167 阅读