2407. Longest Increasing Subsequence II #

解法一：DP #

建立一個 dp array，dp[i]代表的是以nums[i]做為結尾的 seq 的最大長度，做法是搜尋 dp[0] ~ dp[i-1]，找到最大的 sub-LIS，將其+1 更新dp[i]。但為了滿足相鄰的元素相減必須比k小，需要加入nums[i]-nums[j] <=k判斷。

int dp[numsSize];
int max = 1;
for(int i = 0; i < numsSize; i++) {
    dp[i] = 1;
    for(int j = 0; j < i; j++)
        dp[i] = (nums[i]>nums[j] && nums[i]-nums[j] <=k && dp[i] <= dp[j]) ? dp[j]+1: dp[i];
    max = dp[i] > max ? dp[i] : max;
}
return max;

TC: $O(n^2)$

這個解法會因為超時而 TLE ，因為查詢的複雜度過高，要簡化可以使用線段樹優化區間查詢。

解法二：DP+Segment Tree #

解法一的效能瓶頸是每次的查詢都是$n^2$，為了降低區間查詢的複雜度，可以使用線段樹來降低查詢複雜度，但為了維護樹的結構，單點修改的複雜度也提升了。

線段樹 (Segment Tree) #

線段樹是一種高等資料結構，大部分語言的標準函式庫沒有提供類似實作或介面。線段樹的每個節點代表的是聯集左右子樹區間查詢的結果，以此題來說更新 dp[i] 時，只要查詢代表著dp[i-k]~dp[i-1] 的節點就可以了，不必造訪每個葉節點取值。

線段樹主要有三個操作

• 區間查詢
• 單點修改
• 區間修改

但本題只需要用到前兩個，並且因為所有數字結尾的 LIS 長度預設都是 0 ，不用初始化線段樹所以只要實現前兩個功能就好了。

儲存 #

線段樹的儲存可以用陣列或串列，因為是二元樹的關係用陣列一樣可以利用 index 推算出左右子節點的位置。每個節點代表的區間在實作上我習慣用封閉區間 [start, end] 表示，根節點的 index 從 0 或 1 開始都可以，如果用 0 的話左右節點分別是 $2n+1$ 和 $2n+2$，1 的話則是 $2n$ 和 $2n+1$，我以下程式從 0 開始。

假設一個長度為$n$ 的陣列，

• Best Case: $n$ 為 2 的次方，其對應的線段樹是一個滿二元素(full tree)，總節點數為 $2^n-1$。
• Worst Case: $n$ 不是 2 的次方，每層的節點數是前幾層加起來後 +1，總節點數是$4n-1$。

因此 $4n$ 的空間是最小足夠的，上面的推論是我抄來的，我數學很爛ㄏㄏ，另外在 codeforce 有人提出迭代取代遞迴方式的線段數，只需要 $2n$的空間就可以實現。

區間查詢 #

當要查詢的區間 [l, r] 與當前節點表示的區間 [L, R] 完全一致時，回傳此節點的值。 否則取出當前節點的中點 M，確認 [l, r] 在M 的左邊還右邊後只搜尋該半邊，如果橫跨了 M則切分 [l, r] 區間做搜尋。M 要擺在左邊或右邊也是看個人習慣，我都偏左。

int query(int i, int L, int R, int l, int r) {
    if(l == L && r == R)
        return tree[i];
    int M = (L+R)>>1;
    if(M >= r)
        return query(i*2+1, L, M, l, r);
    else if(M < l)
        return query(i*2+2, M+1, R, l, r);
    return max(query(i*2+1, L, M, l, M), query(i*2+2, M+1, R, M+1, r));
}

func (s SegTree) Query(l, r, L, R, i int) int {
    if L==l && R==r {
        return s[i]
    }
    M := (L+R)>>1
    if M >= r {
        return s.Query(l, r, L, M, i*2+1)
    } else if M < l {
        return s.Query(l, r, M+1, R, i*2+2)
    }
    return max(s.Query(l, M, L, M, i*2+1), s.Query(M+1, r, M+1, R, i*2+2))
}