最長的子序列的長度

Question

我不期望在這裏找到解決方案。但是我很難找出可能的錯誤。我覺得這是正確的解決方案，但是，解決方案並沒有通過我所有的測試案例。例如{2,2}。以下是我用暴力手段編寫的代碼（最壞的情況 - 複雜度爲n!）。任何幫助將不勝感激。我並不期待解決方案，但想知道我出錯的地方，以及如何正確解決問題。

package org.practice; 
    import java.util.Arrays; 
    import java.util.HashSet; 
    import java.util.LinkedList; 
    import java.util.List; 

    public class LengthofLIS { 
     int maxLength = 0; 

     public static void main(String[] args) { 
      // TODO Auto-generated method stub 
      LengthofLIS l = new LengthofLIS(); 
      int[] nums = { 2,2 }; 
      l.lengthOfLIS(nums); 
     } 

     public int lengthOfLIS(int[] nums) { 
      if (nums.length == 1) 
       return nums.length; 
      List<Integer> hs = new LinkedList<>(); 
      dfs(nums, 0, 0, nums.length - 1, hs); 
      System.out.println(maxLength); 
      return maxLength; 
     } 

     public void dfs(int[] nums, int index, int length, int end, List<Integer> hs) { 

     if (index > end) { 
      return; 
     } 

     for (int i = index; i <= end; i++) { 

      if (hs.size() == 0) { 
       hs.add(nums[i]); 
       length++; 
      } else if (nums[i] > hs.get(hs.size() - 1)) { 
       hs.add(nums[i]); 
       length++; 
      } 

      else if (nums[i] <= hs.get(hs.size() - 1)) 
       continue; 

      dfs(nums, i + 1, length, end, hs); 
      //System.out.println("Printing " + Arrays.asList(hs)); 
      maxLength = Math.max(maxLength, hs.size()); 

      if (maxLength == nums.length) 
       break; 

      if (hs.size() != 0) { 
       hs.remove(hs.get(hs.size() - 1)); 
       length--; 
      } 
     } 
    } 
    } 

Answer 1

既然你沒有要求任何解決方案，我不會爲您提供一個，而在另一方面，你可以簡單地找到很多答案通過只是一個簡單的搜索。

以下是我從您的代碼明白：

public void dfs(int[] nums, int index, int length, int end, List<Integer> hs) { 
    if (index > end) { 
     return; 
    } 
    for (int i = index; i <= end; i++) { 
     if (hs.size() == 0) { 
      hs.add(nums[i]); 
      length++; 
     } 
     else if (nums[i] > hs.get(hs.size() - 1)) { 
      hs.add(nums[i]); 
      length++; 
     } 
     else if (i == end && nums[i] < hs.get(hs.size() - 1)) { //(1) 
      maxLength = Math.max(maxLength, hs.size()); 
     } 
     else if (nums[i] < hs.get(hs.size() - 1)) 
      continue; 
     dfs(nums, i + 1, length, end, hs); 
     if (hs.size() != 0) { //(2) 
      hs.remove(hs.get(hs.size() - 1)); 
      length--; 
     } 
    } 
} 

1. 你想，要實現什麼？考慮最後一個元素是最大元素的情況，那麼您將始終打印0，因爲您永遠不會設置maxLength。

2. 您的主要問題在這裏。因爲您從列表中遞歸刪除a[i]，a[i+1]。假設你有{2, 3, 100, 4, 5, 6, 1}而不是考慮[2, 3, 4, 5, 6]最長的列表，你的代碼會考慮[2, 4, 5, 6]最長的列表。