【動态規劃】數組最長上升子序列問題（LIS）

相較于最長上升子串問題，LIS問題并不嚴格要求連續的子串，其求解難度也有所提升。

在嘗試将該問題由 n n n規模縮減時，我們不光要考慮 n − 1 n-1 n−1規模的，還需要考慮是以更小規模的子問題。因為對于任何位置結尾的最長子串，無法确定其上一個數字在原始數組的什麼位置。據此，我們定義如下的狀态變量和狀态轉移函數。

狀态變量dp[i]: 以數組nums[i]為結尾的最長子串長度

狀态轉移函數: d p [ i ] = max ⁡ ( d p [ j ] + 1 , 1 ) i f j < i & n u m s [ j ] < n u m s [ i ] dp[i]=\max(dp[j]+1,1) \quad if\quad j<i\&nums[j]<nums[i] dp[i]=max(dp[j]+1,1)ifj<i&nums[j]<nums[i]

在LIS具體的求解時，我們可以利用遞歸或者DP的方式進行。這裡分别介紹多種方法：

方法一：原始的遞歸方法

def LIS_RE(array):
    """
    基于遞歸的算法
    """
    if len(array) == 1:
        return 1

    maxLength = 1
    for i in range(len(array)-1):
        if array[i] < array[-1]:
            maxLength = max(LIS_RE(array[:i+1])+1, maxLength)

    return maxLength
           

方法二：遞歸方法+備忘錄

不難發現，在方法一中有大量重複計算的子問題，我們可以通過建構一張Hashtable記錄這些子問題的結果。

def LIS_RE2(array, cache=dict()):
    """
    在上面的遞歸方法中，不難發現有很多重複的子問題，是以通過hash的形式儲存備忘錄
    cache({index:value})為數組array[index]為子序列末尾的最長子序列長度
    """
    if len(array) == 1:
        return 1

    maxLength = 1
    for i in range(len(array)-1):
        if array[i] < array[-1]:
            if i in cache:
                submaxLength = cache.get(i)
            else:
                submaxLength = LIS_RE(array[:i+1])
            maxLength = max(submaxLength+1, maxLength)

    return maxLength

           

方法三：原始的DP算法

def LIS_DP(array):
    """
    基于DP的算法
    定義狀态： dp[i]包括第i個數在内的最長上升子串長度
    定義轉移方程： dp[i] = max(dp[i], dp[j] + 1)  if j <i and nums[j]<nums[i]
    通過設定父節點，可以追溯具體的子序列
    :param array:
    :return:
    """
    dps = [1 for _ in range(len(array))]     # 初始值
    parents = [-1 for _ in range(len(array))]     # 前序節點處值
    for i in range(1, len(array)):
        for j in range(0, i):
            if array[j] < array[i]:
                if dps[j] + 1 > dps[i]:
                    dps[i] = dps[j] + 1
                    parents[i] = j

    # 發現最大子串長度
    maxLength = 0
    maxEndIndex = -1
    for i in range(len(array)):
        if dps[i] > maxLength:
            maxLength = dps[i]
            maxEndIndex = i

    # 回溯子序列數值
    index = maxEndIndex
    numsList =[]
    while index != -1:
        numsList.append(array[index])
        index = parents[index]

    return maxLength, numsList[::-1]
           

方法四：貪婪算法

前面遞歸算法的時間複雜度為 O ( 2 n ) O(2^n) O(2n)，而DP算法的時間複雜度為 O ( n 2 ) O(n^2) O(n2)，那有沒有複雜度更低的算法呢？

在DP算法中，我們每找以nums[i]為結果的子串，均需要周遊前面的所有0-(i-1)組子串，其實這是沒必要的。我們不妨定義一個length數組，用來記錄各最長子串長度時的各子串末尾數值的最小值，這樣每增加一個新的數字，我們可以視其與length各元素的大小關系來決定拓展length數組或者更新其中的元素。

其具體算法細節和說明見下：

def LIS_greedy(array):
    """
    基于貪心思想的算法
    定義數組lengths: lengths[i]表示長度為i+1的上升子串中對應的最小值, 最終的length長度即為最長序列長度
    其更新思想為：若array[j]>length[-1]，則添加array[j], 否則找到第一個大于該值的length[k]進行替換
    注意傳回的length序列并非真實的最短序列
    :param array:
    :return:
    """
    lengths = [-np.inf]            # 定義一個哨崗位
    for i in range(len(array)):
        if array[i] > lengths[-1]:
            lengths.append(array[i])

        else:
            j = len(lengths) - 1
            while j > 0:
                if lengths[j] > array[i]:
                    j -= 1
                else:
                    break
            lengths[j+1] = array[i]

    return len(lengths) - 1, lengths[1:]
           

該算法仍包含兩層循環，時間複雜度仍為 O ( n 2 ) O(n^2) O(n2)。不難注意到對于length數組而言，其是單調遞增的，是以可以引入二分搜尋進行快速定位，進而将時間複雜度降低為 O ( n l o g n ) O(nlogn) O(nlogn)，具體見下。

方法五 貪婪算法+二分搜尋

def LIS_greedy2(array):
    """
    在上述貪心算法基礎上，注意到lengths序列本身是有序的,可以用二分法加速搜尋，進而使算法的時間複雜度降至O(nlog(n))
    定義數組lengths: lengths[i]表示長度為i+1的上升子串中對應的最小值, 最終的length長度即為最長序列長度
    其更新思想為：若array[j]>length[-1]，則添加array[j], 否則找到第一個大于該值的length[k]進行替換
    注意傳回的length序列并非真實的最短序列
    :param array:
    :return:
    """
    lengths = [-np.inf]
    for i in range(len(array)):
        if array[i] > lengths[-1]:
            lengths.append(array[i])

        else:
            lo = 1
            hi = len(lengths) - 1
            while lo < hi:        # 該值必然存在
                mid = lo + (hi - lo)//2
                if lengths[mid] > array[i]:
                    hi = mid
                else:
                    lo = mid + 1

            lengths[lo] = array[i]

    return len(lengths) - 1, lengths[1:]