ZeroJudge 解題筆記：d242. 00481 - What Goes Up

作者：王一哲
日期：2026年5月13日


ZeroJudge 題目連結：d242. 00481 - What Goes Up

解題想法

這題要找最長遞增子序列 (longest increasing subsequence, LIS) 的內容，網路上有不少的教學。我是記錄目前 lis 對應的字元索引值，最後再將這些索引值對應的字元組成字串，反序後輸出。

Python 程式碼

使用時間約為 0.9 s，記憶體約為 64.9 MB，通過測試。

def get_lis(nums):
    if not nums: return []
    n = len(nums)
    prev = [-1]*n
    tails = []
    for i, num in enumerate(nums):
        low, high = 0, len(tails)-1
        while low <= high:
            mid = (high - low) // 2 + low
            if num > nums[tails[mid]]: low = mid + 1
            else: high = mid - 1
        if low == len(tails): tails.append(i)
        else: tails[low] = i
        if low > 0: prev[i] = tails[low-1]
    lis = []
    curr = tails[-1]
    while curr != -1:
        lis.append(nums[curr])
        curr = prev[curr]
    return lis[::-1]

def solve():
    import sys
    
    result = []
    arr = list(map(int, sys.stdin.read().split()))
    lis = get_lis(arr)
    result.append(f"{len(lis):d}\n-\n")
    for v in lis: result.append(f"{v:d}\n")
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

C++ 程式碼

使用時間約為 75 ms，記憶體約為 8.9 MB，通過測試。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/* 自訂二分搜尋法，找 LIS 內容 
   下一行如果用 vector<int>& nums 會改變 nums 的內容 
   取不同的變數名稱，在函式中複製陣列內容               */
vector<int> get_LIS(vector<int>& arr) {
    vector<int> tails, nums (arr.begin(), arr.end());  // 儲存 LIS 內容於 nums 之中的索引值，複製 arr
    if (nums.empty()) return tails;  // 輸入空陣列，直接回傳空陣列
    int n = (int)nums.size();  // nums 的長度
    vector<int> prev (n, -1);  // 後往前找 LIS 內容時，前一項的索引值
    for(int i=0; i<n; i++) {  // 序取出 nums[0] ~ nums[n-1]
        // nums[i]，二分搜尋法的索引值下限、上限，閉區間
        int num = nums[i], low = 0, high = (int)tails.size()-1; 
        while(low <= high) {  // 二分搜尋法
            int mid = (high - low)/2 + low;  // 中點
            if (num > nums[tails[mid]]) low = mid+1;  // num 較大，提升 low
            else high = mid-1;  // 反之，降低 high
        }
        if (low == (int)tails.size()) tails.push_back(i);  // 的最大值，i 加到 tails 最後面
        else tails[low] = i;  // 反之，取代 tails[low]
        if (low > 0) prev[i] = tails[low-1];  // 如果 low 大於 0，有前一項，更新 prev
    }
    vector<int> lis;  // 儲存 LIS 內容的空串列
    int curr = tails.back();  // 從 nums 讀取資料的索引值
    while(curr != -1) {  // curr 不等於 -1 繼續執行
        lis.push_back(nums[curr]);  // 取出 nums[curr] 加到 lis
        curr = prev[curr];  // 更新 curr
    }
    reverse(lis.begin(), lis.end());  // lis 內容順序相反，反轉 lis
    return lis;  // 回傳 lis
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    vector<int> nums;
    int v;
    while(cin >> v) nums.push_back(v);
    vector<int> lis = get_LIS(nums);
    cout << lis.size() << "\n" << "-\n";
    for(int it : lis) cout << it << "\n";
    return 0;
}