Call a number $\ell$-good if $\ell$ is the smallest number such that $a_k + a_{k+1} + \dots + a_{k+\ell-1} \ge 0$, and $\ell \le m$. Then if $a_k$ is $\ell$-good, the numbers $a_{k+1}, \dots, a_{k+\ell-1}$ are good as well. Then by greedy from left to right, we can group all the good numbers into blocks with nonnegative sums. Repeatedly take the first good number, if $\ell$-good, group it with the next $\ell$ numbers. An example for $m = 3$: \[ \langle 4 \rangle \quad \langle -1 \quad -2 \quad 6 \rangle \quad -9 \quad -7 \quad \langle 3 \rangle \quad \langle -2 \quad 4 \rangle. \] So the sum is nonnegative, done. This solution was motivated by looking at the case $\ell = 1$, realizing how dumb it was, then looking at $\ell = 2$, and realizing it was equally dumb.

This is a special case of the maximal ergodic theorem. I believe Mark Sellke proposed it (at least a couple months ago he said he might).

Should we also worry about wrap around? For instance, if we add $-1$ to the end of the above sequence: \[ \langle 4 \rangle \quad \langle -1 \quad -2 \quad 6 \rangle \quad -9 \quad -7 \quad \langle 3 \rangle \quad \langle -2 \quad 4 \rangle \quad -1\]Then the rightmost $-1$ is good but its block would be $\langle -1 \quad 4 \rangle$, so that in summing up all the positive sets of good indexed terms, we double count $4$. If that is a problem, then I think we could work around it by continuing to greedily form blocks (with wrap around) until we hit the same block again (position-wise in the sequence). If the sequence of blocks is $B_1, B_2, \ldots, B_i, \ldots, B_k$ with $B_i = B_k$ being the first occurrence of a duplicate, then letting $s(B)$ denote the sum of the elements of a block $B$, $\sum_{j=i}^{k-1} s(B_j) \ge 0$ and this sum is some positive integer multiple of $\sum_{k \in T} a_k$.

McTeague: You are correct! I completely missed the part about indices modulo $n$. Fortunately, you can fix this as you did, or as follows. Make $N$ copies of the sequence, and then apply greedy algorithm. Then we get $N \sum_{k \in T} a_k + \text{leftover} \ge 0$. The leftover part is bounded by $\sum |a_i|$, and $N$ can be arbitrarily large, so we're done.

or just bash using functional equations with respect to diophantine. It yields a faster solution.

chemoly2017 wrote: or just bash using functional equations with respect to diophantine. It yields a faster solution. Can you post a full solution? I'm not sure what you mean.

For each $k$, let $f(k)=\max_{1\leq\ell\leq m}\left(\sum_{i=0}^{\ell-1}a_{k+i}\right)$ and take $\ell_k$ achieving this maximum. As $\max_{S\subseteq\{1,\dots,n\}}\left(\sum_{k\in S}f(k)\right)=\sum_{k\in T}f(k)$, $$\sum_{k\in T}a_k=\sum_{k\in T}\left(f(k)-\sum_{i=1}^{\ell_k-1}a_{k+i}\right)\geq\sum_{k\in T}(f(k)-f(k+1))\geq0.$$

It'a so wired that an old CMO problem appears in TSTST CMO1988:https://artofproblemsolving.com/community/c6h561231p3269281

If there are no negative good numbers, we are trivially done. If there are negative good numbers, then it is time for Elmo to do his job. He puts a crayon at the negative good number $a_k$ with $k$ minimal and draws an arc from $a_k$ to $a_{k+\ell-1}$, where $\ell$ is minimal in the condition. Then Elmo tries to find a negative good number after $a_{k+\ell-1}$ and draws an arc in a similar fashion. Elmo repeats this process until one of two things happen. Either the final arc doesn't intersect the first arc, or it does. If the arcs do intersect, Elmo erases all arcs wholly contained within the final arc. Now, by construction, all negative good numbers are contained within some arc, whose sum is non-negative. Furthermore, the only arcs that intersect are possibly the last arc $L$ with some (and at most one) other arc $A$. Then the numbers in $L \cap A$ is a proper subset of the numbers in $A$, so by minimality of $A$, the sum of the numbers in $L \cap A$ is negative. Thus, in any case, the sum of the numbers in some arc is non-negative. But this sum includes all negative numbers in $T$ and possibly some negative numbers, so $\sum_{k \in T} a_k \ge 0$, as desired.

We have the following key claim. Claim: Suppose $i,i+1,\ldots,i+k-1$ are all good, and $i+k$ is bad. Then, \[a_i+a_{i+1}+\cdots+a_{i+k-1}\ge 0.\] Proof: We proceed by induction on $k$. The base case $k=0$ is $0\ge 0$. We have $i$ good, so \[a_i+a_{i+1}+\cdots+a_{i+\ell-1}\ge 0\]for some $1\le\ell\le m$. We have two cases. Case 1: Suppose $1\le\ell\le k$. Then we're done by induction since we have \[a_{i+\ell}+a_{i+\ell+1}+\cdots+a_{i+k-1}\ge 0\]by the claim for $k-\ell$. Case 2: Suppose $\ell\ge k+1$. Then, \[a_{i+k}+a_{i+k+1}+\cdots+a_{i+\ell-1}<0\]as $1\le \ell-k\le m$ and $i+k$ is bad. Thus, \[a_i+a_{i+1}+\cdots+a_{i+k-1}\ge -(a_{i+k}+a_{i+k+1}+\cdots+a_{i+\ell-1})>0,\]so we're done. $\blacksquare$ Note that this solves the problem as long as $|T|<n$, as we can split $T$ into contiguous blocks. It suffices to deal with the case where $|T|=n$, or that all the indices are good. We solve this case by induction on $m$ (!), where the base case of $m=1$ is trivial since it implies $a_i\ge 0$ for all $i$. Now suppose we have all indices good and $m\ge 2$. Let $S$ be the set of indices that are good, but become bad when we replace $m$ with $m-1$. We have the following claim that allows us to carry out the induction. Claim: The following two statements hold. Suppose $i\in S$. Then, for any $j\in[i+1,i+m-1]$, we have \[a_j+a_{j+1}+\cdots+a_{i+m-1}\ge 0.\] Suppose $i\not\in S$. Then, there is some $j$ such that \[a_i+a_{i+1}+\cdots+a_j\ge 0\]and none of $i,i+1,\ldots,j$ are in $S$. Proof: The first statement simply follows from the fact that $a_i+\cdots+a_{j-1}<0$ and $a_i+\cdots+a_{i+m-1}\ge 0$. We will now show the second statement. Suppose the smallest $j$ such that \[a_i+a_{i+1}+\cdots+a_j\ge 0\]satisfies $\ell\in S$ for some $\ell\in[i,j]$. Then, we have $a_\ell+\cdots+a_j<0$ since $j\le i+m-1<\ell+m-1$, so \[a_i+\cdots+a_{\ell-1}\ge 0.\]We can keep removing elements like this until none of the indices are in $S$, so we're done. $\blacksquare$ Back to the induction. The first part of the claim implies that the intervals $[i,i+m-1]$ are disjoint for $i\in S$, so the sum of $a_i$ for those intervals is nonnegative, since $a_i+\cdots+a_{i+m-1}\ge 0$. The rest of the indices have sums that are nonnegative that do not go into these intervals, so we may delete these intervals, and the problem reduces to the case where all the indices are good with $m$ replaced with $m-1$. The inductive hypothesis now finishes.

The problem can be directly approached, as shown above, e.g. in #2. But, I want to show it is an implication of a more general claim - see $(*)$ below. Given a sequence $ a_k,k=1,2,\dots,n$ we define another sequence $ M[a]_k, k=1,2,\dots,n$ by $$ \displaystyle M[a]_k := \max_{1\le \ell\le m}\frac{|a_k|+|a_{k+1}|+\dots+|a_{k+\ell-1}|}{\ell}\,,\,k=1,2,\dots,n$$with appropriate circulation of indices. The sequence $M[a]_k,k=1,\dots,n$ may be considered as a discrete analog of the Hardy-Littlewood maximal function. Like in the continuous case, the following estimate also holds. $$ {\displaystyle \#\{i:M[a]_i\ge \alpha\}\le \frac{1}{\alpha}{\displaystyle\sum_{i : M[a]_i\ge \alpha}|a_i|}\quad (*)}$$Let's now show how $ (*)$ implies the claim of the OP. If all the terms $ a_i,i=1,\dots,n$ are non negative, the result is trivial. So, suppose there are negative terms of the given sequence $ a_i$. Let $ m:=-\min\{a_i:1\le i\le n\}$ and $ b_i:=a_i+m,i=1,2,\dots,n$. We apply $ (*)$ to the non negative sequence $\displaystyle (b_i)_{i=1}^n$ with $ \alpha=m$. It yields $$ \displaystyle \#\{i:M[b]_i\ge m\}\le \displaystyle \frac{1}{m}\sum_{i : M[b]_i\ge m} b_i$$The set in the LHS of the above estimate is just the set $ T$ of good indices of the sequence $ a_i$. Hence $$ |T| \le \displaystyle \frac{1}{m}\sum_{i\in T}(a_i+m)$$$$ \displaystyle \sum_{i\in T}a_i\ge 0$$ Remark. I commented it in more details in my blog.

I'm a little suspicious of the following argument given that other inductive approaches in this thread seem more complicated. Does the following work?

Does this work? Let $\ell{(k)}$ denote the smallest $\ell$-value that makes an index $k$ good. Clearly $a_{k+i}$ is good for all $0\le i\le \ell{(k)} - 1$. Moreover, if there exists a good index $k'$ not among $k$, $k+1$, ..., $k + \ell{(k)} - 1$ such that $k' + \ell{(k')} - 1\equiv k + j\pmod{n}$ for some $0\le j < \ell{(k)} - 1$, we must have $a_{k'} + a_{k'+1} + ... + a_{k-1}\ge 0$ since $a_k + a_{k+1} + ... + a_{k+j} < 0$ by the minimality of $\ell{(k)}$. But this contradicts, the minimality of $\ell{(k')}$, so there exists no such $k'$. Now choose an index $k_2\in T' = T\setminus \{k, k+1, ..., k + \ell{(k)} - 1\}$ with maximal $\ell{(k_2)}$ and $k_2$, $k_2 + 1$, ..., $k_2 + \ell{(k_2)}-1$ will all be good and also in $T'$. Repeating this process, we obtain a partition of $T$ into disjoint blocks of consecutive good indices, each of which have nonnegative sums. We are done.

For each good term $a_k$, consider the smallest $\ell$ such that $a_k+ \cdots + a_{k+\ell-1} \ge 0$. We call the terms $\{a_k,\cdots , a_{k+\ell-1}\}$ the family of the good term $a_k$. Claim: If two families overlap, then one is contained inside the other. Proof: Assume otherwise; let the families be $\{a_u, a_{u+1}, \cdots, a_v\}$ and $\{a_k, a_{k+1}, \cdots , a_{\ell}\}$ where $u<k \le v < \ell$. Then by minimality of families, \begin{align*} a_u+a_{u+1}+ \cdots + a_{k-1}&<0\\ a_k+a_{k+1}+ \cdots + a_v&<0\\ \end{align*}so $a_u+\cdots+a_v<0$, contradiction. Claim: Every term in a family is good. Proof: Let the family be $\{a_k, \cdots , a_{\ell}\}$. For any $k<i\le\ell$, by minimality of the family we have $a_k+\cdots+a_{i-1}<0$, so $a_i+\cdots+a_{\ell}>0$. These two claims clearly solve the problem (in particular, consider all the families that aren't contained in larger families; these ``maximal" families exactly make up all of $T$, and the sum of each of these families is nonnegative by definition).

Define a block to be a contiguous subsequence starting at a good term $a_k$ such that its length $\ell$ is the minimum integer such that the condition $a_k+a_{k+1}+...+a_{k+\ell-1}\ge0$ holds. Note that $a_{k+\ell-1}$ must be non-negative. Now cyclically shift so that $a_n$ is the end of a block; thus both good and non-negative, and assert that no two blocks can overlap. Remark that all the numbers in a block are good, but no number outside a block is good. Note that the sum of all the numbers in all the blocks is equivalent to $\sum\limits_{k \in T}a_k$ which is evidently at least zero.

The set $T$ contains a collection of contiguous blocks of good indices. Note that here, I'm allowing a block to wrap around, so indices $n-2, n-1, n, 1, 2$ would be part of the same block, assuming they are all in $T$. The problem is essentially the following: Key Claim: The sum of elements in a contiguous block of good indices is non-negative. (Assuming the block is maximal, of course. So if the sequence is $-1, -2, 6$ with $m=3$, you can't cheat and say the block is just -1). We need to consider two cases, depending on if all indices are good or not. Case 1: All indices are good. Suppose for the sake of contradiction that $\displaystyle \sum_{k=1}^n a_k < 0$. Define the partial sums $S_0 = 0$ and $S_k = a_1 + a_2 + \cdots + a_k$. We are assuming $S_n < 0$. Let $k^*$ be the index that maximizes $S_{k-1}$, and if there are multiple, pick the largest such $k^*$. We claim that $k^*$ cannot be a good index. Indeed, for any ending index $i$, we have $$a_{k^*} + a_{k^* + 1} + \cdots + a_i = \begin{cases} S_i - S_{k^* - 1} & \text{if } k^* \le i \le n \\ S_i + S_n - S_{k^* - 1} & \text{if } 1 \le i < k^* \end{cases}$$One can check that in both of those cases, the sum is negative due to the maximality of $S_{k^* - 1}$. Case 2: Not all indices are good. Now we have a collection of blocks that have defined start (and end) points. Proving that a contiguous block of good indices has non-negative sum follows from a straightforward induction on the length of the block. Essentially, suppose the block starts at $a_i$. Then, since $i$ is a good index, there must be a $\ell$ such that $$a_i + a_{i + 1} + \cdots + a_{i + \ell - 1} \ge 0$$and clearly $i + 1, i + 2, \ldots, i + \ell - 1$ are all good indices as well. Then, if the block has stuff after $i + \ell - 1$, simply apply the inductive hypothesis on $a_{i + \ell} + a_{i + \ell + 1} + \cdots$.

Let $\{a_k, a_{k + 1}, \dotsb a_{k + x}\}$ be a set of good indices where $a_{k-1}$ and $a_{k+x+1}$ are both bad or we have $x = \ell$ and $a_{k+x+1}$ possibly be good otherwise we have $x < \ell$. If $x = \ell$ our answer is trivial. If we have $x < \ell$ then we must have $a_k > a_{k-1}$ and $a_{k+x} > a_{k+x+1}$ because otherwise those indices would be good. Now, we can see that it is beneficial to leave all other indices when taking our group of good indices. That is \[\sum_{n=y}^{n = x} a_{k+n} > \sum_{n = y}^{n = x+z} a_{k+n}\]Thus we must have that those indices sum to a positive number. $\blacksquare$

Let $k$ be a good index. Let $1 \le l \le m$ be the least positive integer such that $a_k + a_{k+1} + \dots + a_{k+l-1} \ge 0$. Call a range $k, k+1, \dots, k+l-1$ good range. Note that for all positive integer $1 \le s < l-1$, we have $a_k + a_{k+1} + \dots + a_{k+s} < 0$, so $a_{k+l-1} + \dots + a_{k+s+1} > 0$ for all $1 \le s < l-1$. Thus, we can divide $T$ into disjoint good ranges, so $\sum_{k \in T} a_k \ge 0$, as needed. $\blacksquare$

Fairly straightforward. The idea is to divide the good numbers into blocks: Claim: Let $k_1$ and $k_2$ be indices such that $a_{k_1-1}$ and $a_{k_2+1}$ are not good, but $a_{k_1}, a_{k_1+1}, \dots, a_{k_2}$ are all good. It follows that $a_{k_1} + a_{k_2} + \cdots + a_{k_2} \geq 0$. Proof: Let $i_1, i_2, \dots$ be indices with $i_1 = k_1$ such that $a_{i_j} + a_{i_j + 1} + \cdots + a_{i_{j+1} - 1} \geq 0$ for each $j$, and suppose $i_{r+1} > k_2$ for some minimal $r$. If $i_{r+1} = k_2+1$, we are directly done by summing inequalities. Otherwise, it follows that \[a_{i_r} + a_{i_r+1} + \cdots + a_{i_{r+1} - 1} - \left(a_{k_2 + 1} + a_{k_2 + 2} + \cdots + a_{i_{r+1} - 1}\right) \geq 0\]as the first expression is nonnegative by goodness of $a_{i_r}$ and the second expression is negative by badness of $a_{k_2+1}$. Summing this with the previous inequalities once again yields the result. $\blacksquare$ If all the $\{a_i\}$ are good, consider the arrow graph on $[n]$ with an edge $ i \to j$ if $a_i+a_{i+1} + \cdots + a_{j-1} \geq 0$. This graph has no self-loops and every vertex has outdegree at least $1$, so it has a cycle, and summing the inequalities for the terms in the cycle yields the result. Else we can partition the good numbers into sections satisfying the constraints of the claim, which yields the result. Remark: Regarding solutions using the claim above: one has to be a bit careful if all the $a_i$ are good because we don't get a single bad $a_i$ to partition with. Fortunately, that case is easy.

For each $k \in T$, let $\ell_k$ denote the least possible $\ell$ satisfying the conditions, and $a_k + \ldots + a_{k+\ell_k-1}$ as the series of $a_k$. Notice this implies $a_{k+1}, \ldots, a_{k+\ell-1}$ are all good, and the series of each are substrings of the series of $a_k$. Thus all series are either disjoint or substrings/substrings of each other, so we don't need to worry about series with just some overlapping terms. Begin partitioning the sequence into series of good elements by considering the maximal $\ell_k$ and working down. This finishes with series of good elements each having nonnegative sum. $\blacksquare$

I don't know if my solution is correct tho here is mine. (proof by induction of $m$.) We prove by an induction of $m$. if $m=1$, it's obviously true. we call integer $k$ is good for $\ell$ if the condition in the problem satisfied. claim: If $h$ is good for $m$ but not good for $i(1\le i<m)$, then $h+1, h+2,\cdots ,h+m-1$ are all good. proof: For $p$, $a_h+a_{h+1}+\cdots a_{p-1}<0$ thus $a_p+a_{p+1}+\cdots a_{h+m-1}\ge 0$, as desired. thus we can partition $T$ into few set of consecutive numbers and sum of those in $\{ a_i\}$ are nonnegative, so we're done. (it might be awkward because English.)

Not proud of this one