解题思路

这是一个最长上升子序列(LIS)问题，使用二分查找优化。关键点：

  1. 贪心策略：

    • 维护一个递增数组
    • 表示长度为 的上升子序列的最小末尾元素

  2. 二分查找：

    • 对于每个数字，在 中找到第一个大于它的位置
    • 更新该位置的值为当前数字

  3. 结果：

    • 数组的长度就是最长上升子序列的长度
    • 数组不一定是真实的最长上升子序列

代码

class AscentSequence {
public:
    int findLongest(vector<int>& A, int n) {
        if(n == 0) return 0;
        vector<int> dp;
        dp.push_back(A[0]);
        
        for(int i = 1; i < n; i++) {
            if(A[i] > dp.back()) {
                dp.push_back(A[i]);
            } else {
                int pos = lower_bound(dp.begin(), dp.end(), A[i]) - dp.begin();
                dp[pos] = A[i];
            }
        }
        
        return dp.size();
    }
};

import java.util.*;

public class AscentSequence {
    public int findLongest(int[] A, int n) {
        // write code here
        if(n == 0) return 0;
        int[] dp = new int[n];
        int len = 0;
        dp[0] = A[0];
        
        for(int i = 1; i < n; i++) {
            if(A[i] > dp[len]) {
                dp[++len] = A[i];
            } else {
                int pos = binarySearch(dp, 0, len, A[i]);
                dp[pos] = A[i];
            }
        }
        
        return len + 1;
    }
    
    private int binarySearch(int[] dp, int left, int right, int target) {
        while(left <= right) {
            int mid = left + (right - left) / 2;
            if(dp[mid] >= target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

# -*- coding:utf-8 -*-

class AscentSequence:
    def findLongest(self, A, n):
        if n == 0:
            return 0
            
        dp = [A[0]]
        
        for i in xrange(1, n):
            if A[i] > dp[-1]:
                dp.append(A[i])
            else:
                left, right = 0, len(dp) - 1
                while left <= right:
                    mid = (left + right) // 2
                    if dp[mid] >= A[i]:
                        right = mid - 1
                    else:
                        left = mid + 1
                dp[left] = A[i]
        
        return len(dp)

算法及复杂度

  • 算法：贪心 + 二分查找
  • 时间复杂度：，每个元素需要一次二分查找
  • 空间复杂度：，需要 数组存储