一、最長遞增子序列問題概述

1. 問題定義

給定一個整數(shù)序列，例如 nums = [10, 9, 2, 5, 3, 7, 101, 18]，要找出它的一個最長的子序列，使得這個子序列中的元素是嚴(yán)格遞增的。

在上述例子中，最長遞增子序列是 [2, 3, 7, 101] 或者 [2, 5, 7, 101] 等，長度為 4。

2. 常規(guī)動態(tài)規(guī)劃解法思路及缺點

思路：

• 通常可以定義一個 dp 數(shù)組，其中 dp[i] 表示以 nums[i] 為結(jié)尾的最長遞增子序列的長度。
• 狀態(tài)轉(zhuǎn)移方程一般為 dp[i] = max(dp[j]) + 1（其中 0 <= j < i 且 nums[j] < nums[i]），也就是遍歷前面所有小于 nums[i] 的元素對應(yīng)的 dp 值，取最大的那個再加 1 來更新 dp[i]。
• 最后整個序列的最長遞增子序列長度就是 dp 數(shù)組中的最大值。

缺點：

• 這種常規(guī)解法的時間復(fù)雜度是 ，當(dāng)輸入序列長度 n 較大時，效率會比較低
• 所以需要進行優(yōu)化來降低時間復(fù)雜度，提升求解效率

二、優(yōu)化解法一：貪心 + 二分查找（時間復(fù)雜度優(yōu)化至nlogn ）

1. 貪心思想

維護一個數(shù)組 tail，它用來存儲當(dāng)前找到的最長遞增子序列的 “尾巴” 元素，這個數(shù)組的長度其實就代表了當(dāng)前找到的最長遞增子序列的長度（初始時長度為 0）。

對于新遍歷到的元素 nums[i]，我們希望以一種貪心的策略把它盡可能合理地添加到 tail 數(shù)組中，使得 tail 數(shù)組始終保持一種有序的狀態(tài)（因為遞增子序列的特性決定了 “尾巴” 元素是有序遞增的），這樣就能通過后續(xù)的操作高效地找到最長遞增子序列。

2. 二分查找的運用

每當(dāng)遍歷到一個新元素 nums[i] 時，我們在 tail 數(shù)組中通過二分查找找到第一個大于等于 nums[i] 的元素位置 pos（可以利用 Java 中的 Arrays.binarySearch 等二分查找相關(guān)方法實現(xiàn)，若沒找到則返回插入點，即合適的位置）。

• 如果 pos 等于 tail 數(shù)組當(dāng)前長度，說明 nums[i] 比當(dāng)前所有的 “尾巴” 元素都大，那它就可以作為新的 “尾巴” 元素添加到 tail 數(shù)組末尾，使得最長遞增子序列長度加 1，即 tail = Arrays.copyOf(tail, tail.length + 1); tail[tail.length - 1] = nums[i];。
• 如果 pos 小于 tail 數(shù)組當(dāng)前長度，說明 nums[i] 可以替換掉 tail[pos]，因為這樣做不會破壞遞增子序列的性質(zhì)，而且有可能在后續(xù)找到更長的遞增子序列，即 tail[pos] = nums[i];。

3. Java 代碼示例

import java.util.Arrays;

public class LongestIncreasingSubsequence {
    public static int lengthOfLIS(int[] nums) {
        int[] tail = new int[nums.length];
        int len = 0;
        for (int num : nums) {
            int pos = Arrays.binarySearch(tail, 0, len, num);
            if (pos < 0) {
                pos = -(pos + 1);
            }
            tail[pos] = num;
            if (pos == len) {
                len++;
            }
        }
        return len;
    }

    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        int result = lengthOfLIS(nums);
        System.out.println("最長遞增子序列長度為: " + result);
    }
}

在上述代碼中：

• lengthOfLIS 方法實現(xiàn)了優(yōu)化后的最長遞增子序列求解邏輯。通過不斷遍歷輸入數(shù)組 nums，利用二分查找在 tail 數(shù)組中定位合適位置來更新 tail 數(shù)組，同時維護最長遞增子序列的長度 len。
• main 方法進行簡單測試，傳入示例數(shù)組并輸出最終計算得到的最長遞增子序列長度。

三、優(yōu)化解法二：動態(tài)規(guī)劃 + 狀態(tài)壓縮（時間復(fù)雜度仍為O(n^2) ，但空間復(fù)雜度優(yōu)化）

1. 思路

原始動態(tài)規(guī)劃解法中我們使用了一個 dp 數(shù)組來記錄以每個元素為結(jié)尾的最長遞增子序列長度，但是其實在計算 dp[i] 時，我們只需要知道前面元素中小于 nums[i] 的那些元素對應(yīng)的 dp 值情況，并不需要把所有之前元素對應(yīng)的 dp 值都完整保存下來。

所以可以通過狀態(tài)壓縮，只使用一個長度為 n 的一維數(shù)組來模擬動態(tài)規(guī)劃過程，每次更新當(dāng)前元素對應(yīng)的 dp 值時，及時覆蓋之前不再需要的值，從而節(jié)省空間。

2. Java 代碼示例

public class LongestIncreasingSubsequence {
    public static int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int maxLen = 1;
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        int result = lengthOfLIS(nums);
        System.out.println("最長遞增子序列長度為: " + result);
    }
}

在這個代碼示例中：

• lengthOfLIS 方法里，通過一個一維的 dp 數(shù)組來進行動態(tài)規(guī)劃求解，內(nèi)層循環(huán)中不斷更新 dp[i] 的值，并且實時維護最大的最長遞增子序列長度 maxLen，最后返回 maxLen 作為結(jié)果。
• main 方法同樣是用于簡單的測試場景，展示如何調(diào)用 lengthOfLIS 方法并輸出結(jié)果。

通過這些優(yōu)化解法，可以更高效地解決最長遞增子序列問題，在不同的應(yīng)用場景和數(shù)據(jù)規(guī)模下根據(jù)實際需求選擇合適的優(yōu)化方式來提升算法性能。

總結(jié)

以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。

最新評論