Maximum Number of Groups Entering a Competition
You are given a positive integer array grades which represents the grades of students in a university. You would like to enter all these students into a competition in ordered non-empty groups, such that the ordering meets the following conditions:
- The sum of the grades of students in the
i^thgroup is less than the sum of the grades of students in the(i + 1)^thgroup, for all groups except the last. - The total number of students in the
i^thgroup is less than the total number of students in the(i + 1)^thgroup, for all groups except the last.
Return the maximum number of groups that can be formed.
Example 1
Input
grades = [10,6,12,7,3,5]Output
3It is possible to form 3 groups with increasing student counts and grade sums, and it can be shown that more than 3 groups cannot be formed.
Example 2
Input
grades = [8,8]Output
1We can only form 1 group, since forming 2 groups would lead to an equal number of students in both groups.
Constraints
- 1 <= grades.length <= 10^5
- 1 <= grades[i] <= 10^5