LIS 最長(zhǎng)遞增子序列 Java的簡(jiǎn)單實(shí)現(xiàn)
今天遇到了一個(gè)求最長(zhǎng)遞增子序列的問(wèn)題,看了之后就嘗試著用Java實(shí)現(xiàn)了一下,關(guān)于什么是最長(zhǎng)遞增子序列,這里就不在贅述,可以百度或者Google之,以下為實(shí)現(xiàn)的代碼:
說(shuō)明:本段代碼實(shí)現(xiàn)的功能為
(1)隨機(jī)生成一個(gè)有10個(gè)元素的數(shù)組,然后輸出它的最長(zhǎng)遞增子序列
(2)輸出以其中某一個(gè)元素為結(jié)尾的最長(zhǎng)遞增子序列的長(zhǎng)度
具體的實(shí)現(xiàn)思路在注釋中已經(jīng)詳細(xì)表明了,比較簡(jiǎn)單,這里就不再贅述
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("最長(zhǎng)遞增子序列的長(zhǎng)度為"); 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];//用于記錄當(dāng)前個(gè)元素作為最大元素的最長(zhǎng)遞增序列的長(zhǎng)度 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]) { //得到當(dāng)前最長(zhǎng)遞增序列的長(zhǎng)度以及該子序列的最末元素的位置 max=lisLength[i]; } } } System.out.println(max); System.out.println("第i個(gè)元素結(jié)尾時(shí)最長(zhǎng)遞增子序列:"+Arrays.toString(lisLength)); //輸出數(shù)組 } }
以上就是小編為大家?guī)?lái)的LIS 最長(zhǎng)遞增子序列 Java的簡(jiǎn)單實(shí)現(xiàn)的全部?jī)?nèi)容了,希望對(duì)大家有所幫助,多多支持腳本之家~
相關(guān)文章
Java如何對(duì)方法進(jìn)行調(diào)用詳解
今天給大家整理了Java如何對(duì)方法進(jìn)行調(diào)用,文中有非常詳細(xì)的介紹及代碼示例,對(duì)正在學(xué)習(xí)java的小伙伴們很有幫助,需要的朋友可以參考下2021-06-06Windows系統(tǒng)下Eclipse搭建ESP32編譯環(huán)境及安裝過(guò)程
Ecppse 使用了 ESP-IDF 中的 Makefile 支持。這意味著您需要從創(chuàng)建 ESP-IDF 項(xiàng)目開(kāi)始。您可以使用 github 中的 idf-template 項(xiàng)目,接下來(lái)通過(guò)本文給大家介紹Windows系統(tǒng)下Eclipse搭建ESP32編譯環(huán)境及安裝過(guò)程,感興趣的朋友一起看看吧2021-10-10通過(guò)jstack分析解決進(jìn)程死鎖問(wèn)題實(shí)例代碼
這篇文章主要介紹了通過(guò)jstack分析解決進(jìn)程死鎖問(wèn)題實(shí)例代碼,具有一定借鑒價(jià)值,需要的朋友可以參考下2018-01-01DoytoQuery中關(guān)于N+1查詢問(wèn)題解決方案詳解
這篇文章主要為大家介紹了DoytoQuery中關(guān)于N+1查詢問(wèn)題解決方案詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2022-12-12Java使用PrepareStatement實(shí)現(xiàn)數(shù)據(jù)的插入與查詢操作
這篇文章主要為大家詳細(xì)介紹了Java如何使用PrepareStatement實(shí)現(xiàn)數(shù)據(jù)的插入與查詢操作,文中的示例代碼講解詳細(xì),感興趣的可以了解一下2022-09-09SpringBoot整合freemarker實(shí)現(xiàn)代碼生成器
這篇文章主要為大家詳細(xì)介紹了SpringBoot如何整合freemarker實(shí)現(xiàn)一個(gè)簡(jiǎn)單的代碼生成器,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以了解一下2023-03-03