C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 440K, 提交时间: 2023-01-13 11:38:59

#include<bits/stdc++.h>
int a[105],kl[105],kr[105],ans,n,i,j;
signed main(){
    for(std::cin>>n,i=0;i<n;++i)std::cin>>a[i];
    for(i=0;i<n;++i)for(j=0;j<i;++j)if(a[i]>a[j])kl[i]=std::max(kl[i],kl[j]+1);
    for(i=n-1;i>=0;--i)for(j=n-1;j>i;--j)if(a[i]>a[j])kr[i]=std::max(kr[i],kr[j]+1);
    for(i=0;i<n;++i)ans=std::max(ans,kl[i]+kr[i]);
    std::cout<<n-ans-1;
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 504K, 提交时间: 2019-08-30 21:31:41

#include<bits/stdc++.h>
using namespace std;
int n,a[120],al[120],ar[120],q[120],ans,i,j;
int main()
{
    cin>>n;
    for(i=1;i<=n;i++)cin>>a[i];
    for(i=1;i<=n;i++)for(j=1;j<i;j++)if(a[i]>a[j])al[i]=max(al[i],al[j]+1);
    for(i=n;i>=1;i--)for(j=n;j>i;j--)if(a[i]>a[j])ar[i]=max(ar[i],ar[j]+1);
    for(i=1;i<=n;i++)ans=max(ans,al[i]+ar[i]);
    cout<<n-ans-1;
}

Python3 解法, 执行用时: 38ms, 内存消耗: 9740K, 提交时间: 2022-07-29 19:13:55

import bisect
  
def d(s):
    t = [9999] * len(s)
    t[0] = s[0]
    r = [1]
    for i in range(1, len(s)):
        pos = bisect.bisect_left(t, s[i])
        r.append(pos+1)
        t[pos] = s[i]
    return r


N = int(input())
s = list(map(int, input().split()))
dp1 = d(s)
dp2 = d(s[::-1])[::-1]
a = max([dp1[i] + dp2[i] for i in range(N)])
print(N - a + 1)