資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Java 最長遞增子序列程式
在本程式中，我們使用Java 程式語言查詢整數陣列中最長遞增子序列 (LIS) 的長度。遞增子序列是指每個數字都大於前一個數字的數字序列。該程式使用動態規劃方法有效地計算最長遞增子序列。此技術涉及使用先前計算的結果構建解決方案。
問題陳述
編寫一個 Java 程式以獲取最長遞增子序列的長度 -
輸入
10, 22, 9, 33, 21, 50, 41, 60
輸出
The length of the longest increasing subsequence is 5
獲取最長遞增子序列長度的步驟
以下是獲取最長遞增子序列長度的步驟 -
- 初始化一個seq_arr陣列，以儲存每個位置的最長遞增子序列長度。
- 根據陣列元素之間的比較更新seq_arr值。
- 在seq_arr中找到最大值以確定最長遞增子序列長度。
- 將最大值作為最長遞增子序列的長度返回。
Java 最長遞增子序列程式
以下是 Java 程式的最長遞增子序列 -
public class Demo{
static int incre_subseq(int my_arr[], int arr_len){
int seq_arr[] = new int[arr_len];
int i, j, max = 0;
for (i = 0; i < arr_len; i++)
seq_arr[i] = 1;
for (i = 1; i < arr_len; i++)
for (j = 0; j < i; j++)
if (my_arr[i] > my_arr[j] && seq_arr[i] < seq_arr[j] + 1)
seq_arr[i] = seq_arr[j] + 1;
for (i = 0; i < arr_len; i++)
if (max < seq_arr[i])
max = seq_arr[i];
return max;
}
public static void main(String args[]){
int my_arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
int arr_len = my_arr.length;
System.out.println("The length of the longest increasing subsequence is " + incre_subseq(my_arr, arr_len));
}
}
輸出
The length of the longest increasing subsequence is 5
程式碼說明
在上面的 Java 程式碼中，名為Demo的類包含一個名為incre_subseq的靜態函式，該函式將陣列和陣列的長度作為引數。在此函式內部，將建立一個新的空陣列。max 變數被賦予值 0。for 迴圈迭代陣列的長度，並且每個元素都初始化為 1。再次迭代for 迴圈，並啟動另一個for 迴圈，該迴圈檢查陣列中的第一個元素是否等於第二個元素，以及陣列（seq_arr，已初始化為全 1）是否具有第一個元素小於第二個元素 + 1。找到seq_arr中元素的最大值並返回。
更新時間： 2024年8月12日
2K+ 次瀏覽
廣告