数据结构
网络
关系数据库管理系统
操作系统
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+ 次浏览
广告