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

1. 問題定義

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

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

2. 常規(guī)動(dòng)態(tài)規(guī)劃解法思路及缺點(diǎn)

思路：

• 通?？梢远x一個(gè) 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] 的元素對(duì)應(yīng)的 dp 值，取最大的那個(gè)再加 1 來更新 dp[i]。
• 最后整個(gè)序列的最長遞增子序列長度就是 dp 數(shù)組中的最大值。

缺點(diǎn)：

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

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

1. 貪心思想

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

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

2. 二分查找的運(yùn)用

每當(dāng)遍歷到一個(gè)新元素 nums[i] 時(shí)，我們?cè)?tail 數(shù)組中通過二分查找找到第一個(gè)大于等于 nums[i] 的元素位置 pos（可以利用 Java 中的 Arrays.binarySearch 等二分查找相關(guān)方法實(shí)現(xiàn)，若沒找到則返回插入點(diǎ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]，因?yàn)檫@樣做不會(huì)破壞遞增子序列的性質(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 方法實(shí)現(xiàn)了優(yōu)化后的最長遞增子序列求解邏輯。通過不斷遍歷輸入數(shù)組 nums，利用二分查找在 tail 數(shù)組中定位合適位置來更新 tail 數(shù)組，同時(shí)維護(hù)最長遞增子序列的長度 len。
• main 方法進(jìn)行簡單測試，傳入示例數(shù)組并輸出最終計(jì)算得到的最長遞增子序列長度。

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

1. 思路

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

所以可以通過狀態(tài)壓縮，只使用一個(gè)長度為 n 的一維數(shù)組來模擬動(dòng)態(tài)規(guī)劃過程，每次更新當(dāng)前元素對(duì)應(yīng)的 dp 值時(shí)，及時(shí)覆蓋之前不再需要的值，從而節(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);
    }
}

在這個(gè)代碼示例中：

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

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

總結(jié)

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

最新評(píng)論