Author, developer, author of the solution: Andriy Stolitniy
The problem statement mentions that we need every sub-segment of length greater than in each of the final arrays to have a non-negative sum. It can be noted that it is sufficient for all sub-segments of lengths and to have a non-negative sum. This is because every segment of length greater than can be split into sub-segments of lengths and , and if they all have a non-negative sum, then the entire segment has a non-negative sum.
Also, splitting the array into smaller arrays can be done implicitly by removing elements from the array. We will maintain dynamic programming values, where dp_{i,j} will represent the maximum number of elements we can keep from the prefix of length , and we kept the last elements, i.e., , i-1, ..., i-j+1. Then, when we add a new element, we can either keep it or remove it. Since we do not consider sub-segments longer than , we can have states dp_{i,0}, dp_{i,1}, dp_{i,2}, dp_{i,3} —
did not take element ,
took element , did not take i-1,
took , i-1, did not take i-2,
took , i-1, i-2, or more.
Then we can make the following transitions:
Then the answer will be
Overall complexity: .