动态规划解法（O(n²)时间复杂度）

虽然动态规划不是本题的最优解（n=100000时O(n²)会超时），但理解其思路对学习算法非常重要。以下是动态规划解决最长严格上升子序列问题的详细方法：

算法思路：

  1. 状态定义：定义dp[i]表示以第i个元素结尾的最长严格上升子序列的长度
  2. 状态转移方程：
    • 对于每个位置i，检查所有j < i
    • 如果arr[j] < arr[i]，则dp[i] = max(dp[i], dp[j] + 1)
  3. 初始化：每个位置的初始值为1（因为单独一个元素就是长度为1的子序列）
  4. 结果获取：遍历dp数组找出最大值

代码实现：

def main():
    n = int(input())
    arr = list(map(int, input().split()))
    
    # 初始化dp数组，每个元素至少可以形成长度为1的子序列
    dp = [1] * n
    
    # 记录最终结果
    ans = 1
    
    # 动态规划填表
    for i in range(1, n):
        for j in range(i):
            # 如果前面的元素小于当前元素，则更新dp[i]
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)
        # 更新全局最大值
        ans = max(ans, dp[i])
    
    print(ans)

if __name__ == "__main__":
    main()

算法分析：

  • 时间复杂度：O(n²) - 嵌套循环遍历所有元素对
  • 空间复杂度：O(n) - 需要额外dp数组存储状态
  • 优点：思路直观，易于理解
  • 缺点：当n=100000时，计算量达到10¹⁰，远超过现代计算机的处理能力（一般1秒处理10⁷次操作）

贪心+二分（O(n log n)时间复杂度）

为了解决这个问题，我们需要找到给定数组中最长的严格上升子序列（LIS）的长度。由于数组长度可能达到100,000，传统的O(n²)动态规划方***超时，因此我们采用O(n log n)的高效算法。

方法思路

  1. 问题分析：最长严格上升子序列问题要求在不改变元素顺序的情况下，找出一个子序列，其中每个元素严格大于前一个元素，并且这个子序列的长度最大。
  2. 关键观察：维护一个动态数组dp，其中dp[i]表示长度为i+1的上升子序列的最小末尾元素。这个数组始终保持严格递增。
  3. 算法选择：使用贪心结合二分查找的方法：
    • 遍历数组中的每个元素。
    • 对于每个元素，使用二分查找在dp数组中找到第一个大于或等于当前元素的位置。
    • 如果该位置在dp数组末尾，则将当前元素添加到dp数组中（扩展了最长上升子序列）。
    • 否则，用当前元素替换dp数组中该位置的元素（保证后续能形成更长的子序列）。
  4. 复杂度分析：遍历数组需要O(n)时间，每个元素的二分查找需要O(log n)时间，因此总时间复杂度为O(n log n)。空间复杂度为O(k)，其中k是最长上升子序列的长度。

解决代码

import bisect

def main():
    n = int(input().strip())
    arr = list(map(int, input().split()))
    
    dp = []
    for num in arr:
        idx = bisect.bisect_left(dp, num)
        if idx == len(dp):
            dp.append(num)
        else:
            dp[idx] = num
            
    print(len(dp))

if __name__ == "__main__":
    main()

代码解释

  1. 输入处理：读取数组长度n和数组arr。
  2. 初始化：创建一个空数组dp，用于存储不同长度上升子序列的最小末尾元素。
  3. 遍历数组：对于数组中的每个元素num：
    • 使用bisect_left在dp数组中查找第一个大于或等于num的位置idx。
    • 如果idx等于dp的长度，说明num大于dp中所有元素，将其添加到dp末尾（扩展了最长上升子序列）。
    • 否则，用num替换dp[idx]（保证后续能形成更长的子序列）。
  4. 输出结果：最终dp数组的长度即为最长严格上升子序列的长度。

此算法高效地利用了二分查找来维护最小末尾元素数组，确保了在处理大规模数据时的时间效率。