Dividing an Array#509

Dividing an Array (Editorial)

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:

dp_{i,0} = \max \left( dp_{i-1,0}, \; dp_{i-1,1}, \; dp_{i-1,2}, \; dp_{i-1,3} \right)
dp_{i,1} = dp_{i-1,0} + 1
dp_{i,2} = dp_{i-1,1} + 1,\ \text{if } a_i + a_{i-1} \ge 0
dp_{i,3} = \max \left( dp_{i-1,2}, \; dp_{i-1,3} \right) + 1,\ \text{if } a_i + a_{i-1} \ge 0\ \text{and } a_i + a_{i-1} + a_{i-2} \ge 0

Then the answer will be

n - \max \left( dp_{n,0}, \; dp_{n,1}, \; dp_{n,2}, \; dp_{n,3} \right).

Overall complexity: .