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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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'来表示 |
|