动态规划

#include<bits/stdc++.h>
using namespace std;

#define debug true

int n;
const int N=5e5+5;
int a[N];
unordered_map<int,vector<int>> mp;
set<int> A;


void work(){
    cin>>n;

    int st=0;//计算初始段数
    a[0]=0;//哨兵
    for(int i=1;i<=n;i++){
        cin>>a[i];

        if(a[i-1]==0&&a[i]!=0) st++;

        if(a[i]!=0){
            mp[a[i]].push_back(i);//保存值对应索引
            A.insert(a[i]);//有序记录值
        }
    } 

    int ans=st;
    for(int x:A){
        if(mp.count(x)){
            for(int i:mp[x]){
                if(a[i-1]==0&&a[i+1]==0) st--;

                if(a[i-1]!=0&&a[i+1]!=0) st++;

                a[i]=0;
            }   
        }

        ans=max(ans,st);
    }

    cout<<ans;
}


int main(){
    work();

    return 0;
}