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≤n≤5×105,1≤ai≤109.
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!