n-最长单峰子序列

#include<iostream>
using namespace std;
const int N=1010;
int a[N],f[N],g[N],w[N];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        f[i]=1;
        for(int j=1;j<i;j++)
            if(a[j]<a[i])
                f[i]=max(f[i],f[j]+1);
    }
    for(int i=n;i>=1;i--)
    {
        g[i]=1;
        for(int j=n;j>i;j--)
            if(a[j]<a[i])
                g[i]=max(g[i],g[j]+1);
    }
    int maxn=-1;
    for(int i=1;i<=n;i++)
    {
        w[i]=f[i]+g[i]-1;
        maxn=max(maxn,w[i]);
    }
    cout<<n-maxn;
    return 0;
}

N = int(input())
n = [int(i) for i in input().split(' ')]
k = 0
def f1(nums):
    if not nums:
        return 0,[]
    dp = []
    for i in range(len(nums)):
        dp.append(1)
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    q = dp[0]
    t = [nums[0]]
    for i in range(1, len(nums)):
        if q < dp[i]:
            q = dp[i]
            t = [nums[i]]
        elif q == dp[i] and nums[i] not in t:
            t.append(nums[i])
    return q, t

def f2(nums):
    d = []
    if not nums:
        return 0,[]
    dp = []
    for i in range(len(nums)):
        dp.append(1)
        d.append(nums[i])
        for j in range(i):
            if nums[i] < nums[j]:
                if dp[i] < dp[j] + 1:
                    dp[i] = dp[j] + 1
                    d[i]=d[j]
    q = dp[0]
    t = [d[0]]
    for i in range(1,len(nums)):
        if q < dp[i]:
            q = dp[i]
            t = [d[i]]
        elif q == dp[i] and d[i] not in t:
            t.append(d[i])
    return q, t
for i in range(N):
    max1,p1 = f1(n[:i])
    max2,p2 = f2(n[i:])
    if len(p1) == 1 and len(p2) == 1 and p1[0] == p2[0]:
        k = max(max1+max2-1,k)
    else:
        k = max(max1+max2, k)
print(N-k)

DP动态规划