PythonでJOI難易度5を埋める #2

B - 最長の階段

考えたこと
白紙のカードが無い場合は連続した部分の最大を考える問題。 白紙のカードが入っている場合は入っていない場合を少し拡張して、[連続部分の長さ、連続部分列の最初の要素、連続部分列の最後の要素]を記録するlistを作って考える。白紙のカードは、「あと一枚で連続になる場所に挿入したい」ので、連続部分列の最初の要素と最後の要素を記録することで、後からどこに入れるのが最適かを確認している。あと一枚で連続になる場所は、今の連続部分列の最後の要素-次の連続部分列の最初の要素 = 2になる場所なので、そこを見つけてansを更新している。

n, k = map(int,input().split())
cards = [int(input()) for _ in range(k)]

cards.sort()

if cards[0] != 0:
    ans = 0
    con = 1
    for i in range(k-1):
        if cards[i+1] - cards[i] == 1:
            con += 1
        else:
            ans = max(ans,con)
            con = 1
    else:
        ans = max(ans,con)
    print(ans)
else:
    ans = 0
    con = 1
    cards.pop(0)
    v = []
    #start = 0
    for i in range(k-2):
        if con == 1:
            start = cards[i]
        if cards[i+1] - cards[i] == 1:
            con += 1
        else:
            v.append([con, start, cards[i]])
            con = 1
    else:
        v.append([con,start,cards[i+1]])

    #print(v)
    for i in range(len(v)-1):
        if v[i+1][1] - v[i][2] == 2:
            ans = max(ans,v[i][0]+v[i+1][0]+1)
    print(ans)