我一直在学习技术面试并正在做DP问题。我遇到了最长递增子序列问题,然后我直接进行了一些递归。我想出了这个解决方案,我认为它非常简单,但它显示了一些错误。但是我不明白它们可能在哪里。我阅读了一些讨论的解决方案,并且了解它们是如何工作的,但我无法理解我的错误在哪里。任何帮助都会很棒!
这是我的解决方案。
public static int lengthOfLIS(int[] nums) {
return lengthOfLIS(nums, 0, 0, 0);
}
public static int lengthOfLIS(int[] nums, int carry, int index, int max){
if(nums.length == 0){
return 0;
}
if(index == nums.length - 1){
return carry;
}
//Checks if nums[index] is bigger than the max which is the last item to be checked.
int temp_carry = carry;
if(nums[index] > max){
temp_carry++;
max = nums[index];
}
//Here i iterate through all the values starting from index and at the same time,
//start a recursive call from zeroes to the next digit, and ask them to return the max between both calls.
for(int i = index; i<nums.length; i++){
max = Math.max(lengthOfLIS(nums, temp_carry, index+1, max), lengthOfLIS(nums, 0, index+1, nums[index+1]));
}
return max;
}```
最佳答案
所以你有几个问题。
首先...
if(index == nums.length - 1) { return carry; }
这将有效地忽略数组中的最后一个值。如果您的最后一个值大于 max
,那么您将不会增加 carry
,因此您总是有可能将长度计数减少 1。
下一个问题是你的for
循环...
for(int i = index; i<nums.length; i++){ max = Math.max(lengthOfLIS(nums, temp_carry, index+1, max), lengthOfLIS(nums, 0, index+1, nums[index+1])); }
老实说,我不太确定您想在这里实现什么目标,因为它实际上非常令人困惑。更大的问题是您完全忽略了 i,这意味着无论循环运行多少次,传递给 lengthOfLIS 的值都将恰好是每次循环迭代都相同。另外,如果您曾经成功达到条件 if(index == nums.length - 1)
那么您返回进位
,这意味着您将执行您 Math.max
函数对返回的 carry
值进行处理,但这与您使用 max
的用途有很大不同,因为您使用的是 max
表示 LIS 末尾的当前最大数字。因此,突然之间,您的 max
变成了您的 carry
,这只会导致一些心理上的后空翻。
最长递增子序列(LIS)问题的要点是找到给定序列的最长子序列的长度,使得子序列的所有元素都按递增顺序排序,这意味着 { 10, 22, 9, 33, 21, 50, 41, 60 } 是 { 10, 22, 33, 50, 60 } (长度 = 5)
试试这个...
public int lengthOfLIS(int[] nums) {
return lengthOfLIS(nums, 0, 0, -1);
}
public int lengthOfLIS(int[] nums, int carry, int index, int max){
if(nums.length == 0){
return 0;
}
if(nums[index] > max) {
carry++;
max = nums[index];
}
int max_carry = carry;
for (int i = index; i < (nums.length - 1); i++) {
int temp_carry = lengthOfLIS(nums, carry, i + 1, max);
if (temp_carry > max_carry) {
max_carry = temp_carry;
}
}
return max_carry;
}
另请注意,初始调用 lengthOfLIS(nums, 0, 0, -1)
有一个 -1
这是因为您的序列可能以 0 开头。 .. { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15},其中LIS为{ 0, 2, 6, 9, 11, 15 }(长度 = 6)。
关于java - 最长递增子序列。错误在哪里?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58835850/