Maybe a DP problem?

Revision en1, by uet23_danh, 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. $$$1 \le n \le 5 \times 10^5, 1 \le a_i \le 10^9$$$.

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(n^2)$$$ solution. Thanks in advance!

History

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