非零段划分

原问题:

对于所有可能的海平面高度，求最大的岛屿数量？

转化问题：

海平面为p时对应的岛屿数量为多少？

原问题和转化问题的关系：

下降过程中最大的岛屿数量为，取所有可能海平面高度出现的岛屿数量的最大值，即

求最大值的过程放在求和的过程中，因此在求和过程中可以优化为

边界:

当p=10000（最大海平面），即为初始海平面，岛屿数量为0

转化问题的递推方程：

当前海平面为岛屿数量为，海平面下降到的变化岛屿数量为,

如何求岛屿的变化数量

n =int(input())
a_=list(map(int,input().split()))
a=[0]
a.append(a_[0])
for i in range(1,n):
    if a_[i]!=a_[i-1]:
        a.append(a_[i])
a.append(0)
b=[0]*10010
sum=0
cnt=0
for i in range(1,len(a)-1):
    if a[i]>a[i-1] and a[i]>a[i+1]:
        b[a[i]]+=1
    if a[i]<a[i-1]and a[i]<a[i+1]:
        b[a[i]]-=1
for i in range(10000,-1,-1):
    sum+=b[i]
    cnt=max(cnt,sum)
print(cnt)