Description
Given nums, count ways to split it into three non-empty parts where each part's sum is in non-decreasing order.
Examples
Input:
nums = [1,2,2,2,5,0]Output:
3Explanation:
Three valid splits.
Input:
nums = [0,3,3]Output:
1Explanation:
With array [0,3,3], there's only one way to split into three subarrays: [0], [3], [3]. The sums are left=0, mid=3, right=3. Since 0 ≤ 3 ≤ 3, this is a valid split.
Input:
nums = [1,1,1,1,1,1]Output:
10Explanation:
With array [1,1,1,1,1,1], the task requires find splits where left sum ≤ mid sum ≤ right sum. Valid splits include: [1],[1],[1,1,1,1] (sums: 1≤1≤4), [1],[1,1],[1,1,1] (sums: 1≤2≤3), [1],[1,1,1],[1,1] (sums: 1≤3≤2 - invalid), [1,1],[1],[1,1,1] (sums: 2≤1≤3 - invalid), [1,1],[1,1],[1,1] (sums: 2≤2≤2), and others. After checking all possibilities, exactly 10 splits satisfy the condition.
Constraints
- •
3 ≤ nums.length ≤ 10⁵