Giả sử chúng ta có một mảng được gọi là nums, chúng ta phải tìm số cách tốt để tách nums mảng này. Câu trả lời có thể quá lớn nên trả về kết quả theo mô-đun 10 ^ 9 + 7. Ở đây, việc chia một mảng (với các phần tử nguyên) là tốt nếu mảng được chia thành ba mảng con liền kề không trống tương ứng từ trái sang phải và tổng của các phần tử ở phía bên trái nhỏ hơn hoặc bằng tổng các phần tử ở phần giữa và tổng các phần tử ở phần giữa nhỏ hơn hoặc bằng tổng các phần tử ở bên phải.
Vì vậy, nếu đầu vào giống như nums =[2,3,3,3,7,1], thì đầu ra sẽ là 3 vì có ba cách tách khác nhau,
- [2], [3], [3,3,7,1]
- [2], [3,3], [3,7,1]
- [2,3], [3,3], [7,1]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- n:=kích thước của nums,
- m:=10 ^ 9 + 7
- ss:=một mảng có kích thước (1 + n) và điền bằng 0
- đối với mỗi chỉ số i và giá trị val tính bằng num, thực hiện
- ss [i]:=ss [i-1] + val
- r:=0, rr:=0, ans:=0
- đối với l trong phạm vi 1 đến n-2, thực hiện
- r:=tối đa của r và l + 1
- while r
- r:=r + 1
- rr:=tối đa của rr và r
- while rr
=ss [rr + 1] - ss [l], do - rr:=rr + 1
- nếu ss [l]> ss [r] - ss [l], thì
- ra khỏi vòng lặp
- nếu ss [r] - ss [l]> ss [n] - ss [r], thì
- chuyển sang lần lặp tiếp theo
- ans:=(ans + rr - r + 1) mod m
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
def solve(nums): n, m = len(nums), 10**9+7 ss = [0] * (1+n) for i, val in enumerate(nums, 1): ss[i] = ss[i-1] + val r = rr = ans = 0 for l in range(1, n-1): r = max(r, l+1) while r < n-1 and ss[r]-ss[l] < ss[l]: r += 1 rr = max(rr, r) while rr < n-1 and ss[n]-ss[rr+1] >= ss[rr+1]-ss[l]: rr += 1 if ss[l] > ss[r]-ss[l]: break if ss[r]-ss[l] > ss[n]-ss[r]: continue ans = (ans+rr-r+1) % m return ans nums = [2,3,3,3,7,1] print(solve(nums))
Đầu vào
[1,7,3,6,5]
Đầu ra
3