大家好,又见面了,我是你们的朋友全栈君。
[java]代码库package com.wzs;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
//求数组中最长递增子序列
public class Test
{
public static void main(String[] args)
{
int a[] =
{
1, -1, 2, -3, 4, -5, 6, -7
};
find1(a);
}
// [1, -1, 2, -3, 4, -5, 6, -7]
// [1, 1, 2, 1, 3, 1, 4, 1]
// 时间复杂度:O(N*N)
public static void find1(int[] a)
{
int length = a.length;
int[] list = new int[length];// 存储第i个元素之前的最长递增序列值
List result = new ArrayList(); // 存储最长递增序列
for (int i = 0; i < length; i++)
{
list[i] = 1;
for (int j = 0; j < i; j++)
{
if (a[j] < a[i] && list[j] + 1 > list[i])
{
list[i] = list[j] + 1;
if (result.isEmpty())
{
result.add(list[j]);
}
if (!result.contains(list[i]))
{
result.add(list[i]);
}
}
}
}
System.out.println(“第i个元素时最长递增序列:” + Arrays.toString(list));
// 寻找list中最大值
int max = list[0];
for (int i = 0; i < length; i++)
{
if (list[i] > max)
{
max = list[i];
}
}
System.out.println(“最长递增序列长度:” + max);
System.out.println(“最长递增序列:” + result);
}
}
//源代码片段来自云代码http://yuncode.net
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/134579.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...