l********n
发帖数: 1038 | 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]);
}
} | S******a
发帖数: 1426 | 2 I think I have done this one before......a ,have to pick up Java again.
【在 l********n 的大作中提到】
: 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)
: {
| s********u
发帖数: 1109 | 3 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];
}
中间这一段写的不太好，尤其是paths[i]的处理，应该用一个变量比如local_prev来记
录j的值，等j全部遍历完了，这时候再处理paths。包括maxlength也是。
应该是
for( int j = 0; j < i; j++){
if(nums[i]>nums[j] && sizes[i] < sizes[j]+1)
{
sizes[i] = sizes[j]+1;
local_prev = j;
}
}
paths[i] = path[j] + num[i] + " ";
if(maxLength < sizes[i])
maxLength = sizes[i]; | s********u
发帖数: 1109 | 4 话说java里面，一个字符串可以直接与数字相加么？
我一般是用 num[i] +'0'来表示 |
|
