c++

#include <bits/stdc++.h>

using namespace std;

const int N=55;
int n;
int R[N]; // 存储导弹序列
int fu[N]; // 上升子序列 
int fd[N]; // 下降子序列
int res;

void dfs(int index, int su, int sd){
    // index: 当前枚举的点的序号
    // su:当前上升子序列存储的数据的个数
    // sd:当前下降子序列促出的数据的个数
    if(su+sd>=res) return;
    if(index==n){
        res = su+sd;;
        return;
    }

    // case 1:数据在上升子序列中
    int k=0;
    while(k<su && fu[k]>=R[index]) ++k; 
    int v=fu[k]; // 回溯, 备份
    fu[k]=R[index];
    if(k<su) dfs(index+1, su, sd); // 如果数据没有放到上升子序列中, 继续考察下一个数据
    else dfs(index+1, su+1, sd); // 如果放到了上升序列中, 则需要对上升子序列存储个数加1后继续考察
    fu[k]=v; // 恢复现场

    // case 2:数据在下降子序列中
    k=0;
    while(k<sd && fd[k]<=R[index]) ++k;
    v=fd[k];
    fd[k]=R[index];
    if(k<sd) dfs(index+1, su, sd);
    else dfs(index+1, su, sd+1);
    fd[k]=v;


}


int main(){
    while(cin>>n, n){
        for(int i=0; i<n; ++i) cin>>R[i];
        res = n;
        memset(fu, 0x00, sizeof fu);
        memset(fd, 0x00, sizeof fd);
        dfs(0, 0, 0);
        cout<<res<<endl;
    }

    return 0;
}

python

from typing import List
class Solution:
    def main(self, n:int, a:List[int]):
        res=n
        f, g=[0 for _ in range(n)], [0 for _ in range(n)]
        def dfs(i, su, sd):
            nonlocal res
            if su+sd>=res: return
            if i==n: 
                res=su+sd
                return

            k=0
            while k<su and f[k]>=a[i]: k+=1
            t=f[k]
            f[k]=a[i]
            if k<su: dfs(i+1, su, sd)
            else: dfs(i+1, su+1, sd)
            f[k]=t

            k=0
            while k<sd and g[k]<=a[i]: k+=1
            t=g[k]
            g[k]=a[i]
            if k<sd: dfs(i+1, su, sd)
            else: dfs(i+1, su, sd+1)
            g[k]=t

        dfs(0, 0, 0)
        print(res)


if __name__ == '__main__':
    while(1):
        n=int(input())
        if not n: break
        a=list(map(int, input().split()))
        sol=Solution()
        sol.main(n, a)