[Python知识库]python解决最长有序子序列

本博文源于《程序设计竞赛入门》，本文旨在解决最长有序子序列，最长有序子序列是一个动态规划问题。文章共分为：①原题再现 ②测试效果 ③源码思路分析 ④源码完整。

一、原题再现

对于给定一个数字序列($a_1,a_2,...,a_n$),如果满足$a_1<a_2<...<a_n$,则称该序列是有序的。若在序列$(a_1,a_2,...,a_n)$中删除若干元素得到的子序列是有序的，则该子序列为一个有序子序列。有序子序列中长度最大的即为最长有序子序列。
例如，（1，3，5）、（3，5,8）（1,3，5,9）等都是序列（1,7，3,5，9，4,8）的有序子序列；而（1,3,5，9）（1,3，5,8）（1,3，4,8）都是序列(1,7,3,5,9,4,8)的一个最长有序子序列，长度为4.

Input

首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试数据第一行输入一个整数n（$1\le n\le 100$）,第二行输入n个整数，数据范围都在[0,10 000],数据之间以一个空格分隔

Output

对于每组测试，输出n个整数所构成序列的最长有序子序列的长度。每组测试的输出之间留一个空行。

Input
1
7
1 7 3 5 9 4 8

Output
4

二、测试效果

三、源码思路分析

def los(v):
    n = len(v) 
    f = [1] * n 
    for i in range(1,n): 
        for j in range(0,i): 
            if v[i] > v[j] and f[j] + 1 > f[i]: 
                f[i] = f[j] + 1
    return max(f)

设n个整数存在v列表中，DP的四要素如下：

1. 状态：以f(i)表达，表示以下标为i的元素(v[i])为尾元素的最长上升子序列的长度。
2. 转移方程:f(i)=max(f(j)+1,f(i)),其中$o\le j<i且v[i]>v[j]$,寻找以某个$v[j](0\le j<i)$结尾的最长的上升子序列，然后将v[i]添加到子序列的尾部，构成最长的有序子序列（长度增1）
3. 初值:f(i)=1,其中$0\le i<n$，每个数本身可以构成长度为1的上升序列
4. 结果:max(f(i)),其中$0\le i<n$

四、完整源码

def los(v):
    n = len(v) 
    f = [1] * n 
    for i in range(1,n): 
        for j in range(0,i):
            if v[i] > v[j] and f[j] + 1 > f[i]: 
                f[i] = f[j] + 1
    return max(f)

if __name__ == '__main__':
    T = int(input())
    for t in range(T):
        n = int(input())
        a = list(map(int,input().split()))
        if t>0:
            print()
        print(los(a))