java - 最长递增子序列。错误在哪里？

Question

我一直在学习技术面试并正在做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;
  }```

Answer 1

所以你有几个问题。

首先...

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)。