LIS 最長遞增子序列 Java的簡單實現(xiàn)
今天遇到了一個求最長遞增子序列的問題,看了之后就嘗試著用Java實現(xiàn)了一下,關于什么是最長遞增子序列,這里就不在贅述,可以百度或者Google之,以下為實現(xiàn)的代碼:
說明:本段代碼實現(xiàn)的功能為
(1)隨機生成一個有10個元素的數(shù)組,然后輸出它的最長遞增子序列
(2)輸出以其中某一個元素為結尾的最長遞增子序列的長度
具體的實現(xiàn)思路在注釋中已經(jīng)詳細表明了,比較簡單,這里就不再贅述
import java.util.Arrays; import java.util.Random; public class LIS { public static void main(String[] args){ System.out.println("generating a random array..."); LIS lis=new LIS(); int[] oldArray=lis.randomArray(); for (int i = 0; i < oldArray.length; i++) { System.out.print(oldArray[i]+" "); } System.out.println(); System.out.println("最長遞增子序列的長度為"); lis.lisGet(oldArray); } public int[] randomArray(){ Random random=new Random(); int[] randomArray=new int[10]; for (int i = 0; i < 10; i++) { randomArray[i]=random.nextInt(10); } return randomArray; } public void lisGet(int[] arrayL ){ int[] lisLength=new int[arrayL.length];//用于記錄當前個元素作為最大元素的最長遞增序列的長度 for (int i = 0; i < arrayL.length; i++) { //初始化 lisLength[i]=1; } int max=1; for (int i = 1; i < arrayL.length; i++) { for (int j = 0; j <i; j++) { if (arrayL[j]<arrayL[i]&&(lisLength[j]+1)>lisLength[i]) { lisLength[i]=lisLength[j]+1; } if (max<lisLength[i]) { //得到當前最長遞增序列的長度以及該子序列的最末元素的位置 max=lisLength[i]; } } } System.out.println(max); System.out.println("第i個元素結尾時最長遞增子序列:"+Arrays.toString(lisLength)); //輸出數(shù)組 } }
以上就是小編為大家?guī)淼腖IS 最長遞增子序列 Java的簡單實現(xiàn)的全部內(nèi)容了,希望對大家有所幫助,多多支持腳本之家~
相關文章
Windows系統(tǒng)下Eclipse搭建ESP32編譯環(huán)境及安裝過程
Ecppse 使用了 ESP-IDF 中的 Makefile 支持。這意味著您需要從創(chuàng)建 ESP-IDF 項目開始。您可以使用 github 中的 idf-template 項目,接下來通過本文給大家介紹Windows系統(tǒng)下Eclipse搭建ESP32編譯環(huán)境及安裝過程,感興趣的朋友一起看看吧2021-10-10Java使用PrepareStatement實現(xiàn)數(shù)據(jù)的插入與查詢操作
這篇文章主要為大家詳細介紹了Java如何使用PrepareStatement實現(xiàn)數(shù)據(jù)的插入與查詢操作,文中的示例代碼講解詳細,感興趣的可以了解一下2022-09-09SpringBoot整合freemarker實現(xiàn)代碼生成器
這篇文章主要為大家詳細介紹了SpringBoot如何整合freemarker實現(xiàn)一個簡單的代碼生成器,文中的示例代碼講解詳細,感興趣的小伙伴可以了解一下2023-03-03