Haidora and tubes (Editorial)

Solution

It's optimal to sort the tubes , since this allows us efficiently to get the maximum number of blocks , we can use built-in merge sort function which works in \mathcal{O}(n\log n) (or even hand-written one i.e. Bubble sort which works in \mathcal{O}(n^2)) , and after that we compute the maximum number of tubes we can link by iterating through the sorted array and accumulating the block , if it cannot be extended anymore we store it's length to array of blocks sizes $S$ , and the answer will finally be \max_{1 \le i \le |S|} S_i.

Complexity will be \mathcal{O}(n^2) or \mathcal{O}(n \log n) depending on the implementation.

def solve():
    n=int(input())
    a=list(map(int,input().split()))
    a.sort()
    cur=1
    S=[]
    for i in range(n-1):
        if(a[i+1]-a[i]<2):
            cur+=1
        else:
            S.append(cur)
            cur=1
    S.append(cur)
    print(max(S))

for _ in range(int(input())):
    solve()