[Python知识库]csp 202109-2 非零段划分（python）

思想来自这位大佬的第三个方法：

??????CCF202109-2 非零段划分（100分）【序列处理】_海岛Blog-CSDN博客_ccf非零段划分

 ??????????????????????????????????????????????????????????????

n = int(input())
a = list(map(int,input().split()))
b = []
b.append(a[0])
i = 0
for i in range(1,n):    #消除相邻重复的数
    if a[i-1] != a[i]:
        b.append((a[i]))
x = max(b) #用x来存储列表b中的最大的数
c = [ 0 for i in range(10001)] # c 的索引就表示 水位下降到这个索引时 非零段（山峰）是增加1 还是减少了1

b.insert(0,0) #在第一个索引之前加入一个0  方便去比较
b.append(0) #在最后加入0

for i in range(1,len(b)-1):
    if b[i-1] < b[i] and b[i] > b[i+1]: #若比相邻的俩个数都大，就说明下降到这个水位后 非零段增加1
        c[b[i]] += 1
    elif b[i-1] > b[i] and b[i] <b[i+1]: # 若小就会把旁边的俩个非零段连接起来，非零段减少1
        c[b[i]] -= 1
max = 0
sum = 0 # 后缀和
for i in range(x,-1,-1): #因为水位是从最高的开始下降，所以需要后缀和，来判断下降到某一个水位时是增加还是减少。
    sum += c[i]
    if max < sum: #用max来记录最大的非零段
        max = sum
print(max)