Processing math: 100%
Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

Maybe a DP problem?

Revision en1, by aaronlee27, 2023-10-19 07:38:55

Given an array a, you have to divide this array into maximum numbers of continous subarrays that the sum of a subarray is greater or equal to every subarrays that come after it. 1n5×105,1ai109.

Example:

Input

4
6 5 2 3

Output

3

A possible solutions:

6 | 5 | 2 3

Can anyone help me with this problems? I only came up with O(n2) solution. Thanks in advance!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English aaronlee27 2023-10-19 07:38:55 482 Initial revision (published)

×
Can't find such blog