LeetCode 300. Longest Increasing Subsequence（最長遞增子序列）

問題描述

• Given an unsorted array of integers, find the length of longest increasing subsequence.

  For example,

  Given [10, 9, 2, 5, 3, 7, 101, 18],

  The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

• Your algorithm should run in O(n^2) complexity.
• Follow up: Could you improve it to O(n log n) time complexity?
• 位址

問題分析

• 方法1 ：暴力遞歸

  如果用暴力遞歸的話，若求 [i ~ end] 的最長上升子序列的長度，對nums[i]有要或不要兩種決策，如果nums[i] 大于上一個值，那麼這兩種決策中的最大值便即為所求。如果改寫動态規劃的話，有種最優子結構的意思。

  時間複雜度 ：

  O(2^N)

• 方法2 ：記憶化搜尋

  可以用記憶化搜尋來優化上述遞歸過程，為了節省空間，可以用

  preIndex

  來代替遞歸中

  preValue

  的作用。

  時間複雜度：

  O(N^2)

• 方法3 ：動态規劃

  如果換一個思路，用子數組那種經典套路，求以某一位置結尾或者開頭的最優解，然後最終的最優解一定在上述最優中選優。

  用

  length[i]

  表示必須以

  nums[i]

  結束的最長子序列的長度。那麼可以根據

  length[0],length[1]...length[i - 1]

  來得到

  length[i]

  ,具體見實作。最終最長子序列的長度一定是

  length[i]

  中的最大值

  當然，該題也可以用

  length[i]

  表示必須以

  nums[i]

  開頭的最長子序列的長度，從右向左更新即可。

  時間複雜度：

  O(N^2)

• 方法4 ：二分查找法

  首先明确二分查找的特點：如果待查找元素

  num

  不在已排序數組中，那麼查找結束後，最終

  left

  停在剛剛大于

  num

  的位置，

  right

  停在剛剛小于

  num

  的位置。

  然後過程是這樣的：

  

• 對于以上四種方法，LeetCode discuss 中都有提到。

經驗教訓

• 對比方法1與方法3來看，如果我們狀态選取的不一樣，最終算法時間複雜度也不一樣*最優子結構與子數組常用套路*的一種決策，
• 二分查找後

  left

  與

  right

  的性質。

代碼實作

• 暴力遞歸（TLE）

public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == ) {
            return ;
        }
        return maxLenOfLIS(nums, , Integer.MIN_VALUE);
    }
    //傳回[i ~ end] 的最長遞增子序列：要不要nums[i]
    public int maxLenOfLIS(int[] nums, int i, int preValue) {
        if (i== nums.length) {
            return ;
        }
        int maxLen = ;
        if (nums[i] > preValue) {
            maxLen =  + maxLenOfLIS(nums, i + , nums[i]);
        }
        maxLen = Math.max(maxLen, maxLenOfLIS(nums, i + , preValue));
        return maxLen;
    }
           

• 記憶化搜尋

public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == ) {
            return ;
        }
        int[][] memory = new int[nums.length][nums.length + ];
        return maxLenOfLIS(nums, , -, memory);
    }

    public int maxLenOfLIS(int[] nums, int i, int preIndex,int[][] memory) {
        if (i == nums.length) {
            return ;
        }
        if (memory[i][preIndex + ] > ) {
            return memory[i][preIndex + ];
        }
        int maxLen = ;
        if (preIndex == - || nums[i] > nums[preIndex] ) {
            maxLen =  + maxLenOfLIS(nums, i + , i, memory);
        }
        maxLen = Math.max(maxLen, maxLenOfLIS(nums, i + , preIndex, memory));
        memory[i][preIndex + ] = maxLen;
        return maxLen;
    }
           

• 動态規劃

public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == ) {
            return ;
        }
        int[] length = new int[nums.length];
        int maxLen = ;
        //length[i] :表示必須以nums[i]結束的最長子序列的長度
        for (int i = ; i < nums.length; ++i) {
            //初始化為 1
            length[i] = ;
            for (int j = ; j < i; ++j) {
                //周遊前面元素，看能否更新length[i]
                if (nums[i] > nums[j]) {
                    length[i] = Math.max(length[i], length[j] + );
                }
            }
            //更新最大長度
            maxLen = Math.max(length[i], maxLen);
        }
        return maxLen;
    }
           

• 二分查找

public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length ==) {
            return;
        }
        int[] lis = new int[nums.length];
        //LIS的長度
        int len =;
        for (int num : nums) {
            //利用二分法，最終left停在剛好比num大的位置
            int left =;
            int right = len -;
            while(left <= right) {
                int mid = left + (right - left) /;
                if (num > lis[mid]) {
                    left = mid +;
                }else {
                    right = mid -;
                }
            }
            //用num替代該元素
            lis[left] = num;
            //看是否是新增加了元素，若是，則更新len
            len = left == len ? len + : len; 
        }
        return len;
    }