Code is cheap, and ideas are the only thing that matters.

First, let’s preprocess the prefix and sum of the array and make it as a S array. it cost O(n) time complexity.

Then we sort S arrays from small to large, obviously the range of S arrays is n, we can use bucket sort, it will take O (n) time complexity.

Let’s start with the smallest value of the S array. Let’s set it to S_i, and record the minimum subscript that appears with a variable p, initial p = n + 1.

So for each current S_i, ans = max(ans, i - p), after each layer of S_i is traversed, p is updated once that p = min(p, i). it will take O (n) time complexity.

So it will take O (n) time complexity.