最长连续递增子序列(部分有序)

Java基础

浏览数:233

2019-10-8

题目:(1,9,2,5,7,3,4,6,8,0,)中最长的递增子序列为(3,4,6,8)。

代码:

 1 public class 最长递增子序列 {
 2 
 3     public static void main(String[] args) {
 4         int []arr = {0,1,0,1,2,3,1,2,0,1,2,3,4,5,1};
 5         getLargestLen(arr);
 6 
 7     }
 8 
 9     private static void getLargestLen(int[] arr) {
10         int begin=0;     // 最长递增子序列长度的开始位
11         int maxLen = 1; // 最长递增子序列长度
12         int k = 1;  // 递增子序列长度
13         for (int end = 1; end < arr.length; end++) {
14             if(arr[end]>=arr[end-1]){
15                 k++;
16             } else {
17                 k=1;
18             }
19             if (k>=maxLen) {
20                 maxLen = k;
21                 begin = end-maxLen+1;
22             }
23         }
24         System.out.print("最长连续递增子序列为:");
25         for(int i = begin;i<begin+maxLen;i++)
26             System.out.print(arr[i] + "   ");
27     }
28 
29 }

结果:

  

 

作者:|旧市拾荒|