这段LIS为啥崩溃?# JobHunting - 待字闺中
l*n
1 楼
longest Increasing Subsequence问题,java
public class LIS {
public static void main(String[] args)
{
int[] nums = {2,6,4,5,1,3};
printLIS(nums);
}
public static void printLIS(int[] nums)
{
String[] paths = new String[nums.length];
int[] sizes = new int[nums.length];
for(int i=0; i {
sizes[i] = 1;
paths[i] = nums[i] + " ";
}
int maxLength=1;
for(int i=1; i {
for(int j=0; j{
if(nums[i]>nums[j] && sizes[i] < sizes[j]+1)
{
sizes[i] = sizes[j]+1;
paths[i] = paths[j] + nums[i] + " ";
if(maxLength < sizes[i])
maxLength = sizes[i];
}
}
}
for(int i=1; i {
if(sizes[i] == maxLength)
System.out.println("LIS: "+paths[i]);
}
}
public class LIS {
public static void main(String[] args)
{
int[] nums = {2,6,4,5,1,3};
printLIS(nums);
}
public static void printLIS(int[] nums)
{
String[] paths = new String[nums.length];
int[] sizes = new int[nums.length];
for(int i=0; i
sizes[i] = 1;
paths[i] = nums[i] + " ";
}
int maxLength=1;
for(int i=1; i
for(int j=0; j{
if(nums[i]>nums[j] && sizes[i] < sizes[j]+1)
{
sizes[i] = sizes[j]+1;
paths[i] = paths[j] + nums[i] + " ";
if(maxLength < sizes[i])
maxLength = sizes[i];
}
}
}
for(int i=1; i
if(sizes[i] == maxLength)
System.out.println("LIS: "+paths[i]);
}
}