สมมติว่าเรามีอาร์เรย์ชื่อ nums เราต้องหาจำนวนวิธีที่ดีในการแบ่งอาร์เรย์ nums นี้ คำตอบอาจใหญ่เกินไป จึงต้อง return ผลลัพธ์ modulo 10^9 + 7 ในที่นี้ การแบ่งอาร์เรย์ (ที่มีองค์ประกอบเป็นจำนวนเต็ม) ถือว่าดี หากอาร์เรย์ถูกแบ่งเป็นสามซับอาร์เรย์ที่ไม่ว่างและติดต่อกัน ตามลำดับจากซ้ายไปขวา และผลรวมขององค์ประกอบด้านซ้ายน้อยกว่าหรือเท่ากับผลรวมส่วนกลาง และผลรวมส่วนกลางน้อยกว่าหรือเท่ากับผลรวมด้านขวา
เช่น ถ้าอินพุตคือ nums = [2,3,3,3,7,1] ผลลัพธ์จะเป็น 3 เพราะมีสามวิธีแบ่งที่แตกต่างกัน:
- [2],[3],[3,3,7,1]
- [2],[3,3],[3,7,1]
- [2,3],[3,3],[7,1]
วิธีแก้ปัญหา
- n := ขนาดของ nums, m := 10^9+7
- ss := อาร์เรย์ขนาด (1+n) เติม 0
- สำหรับแต่ละดัชนี i และค่า val ใน nums: ss[i] := ss[i-1] + val
- r := 0, rr := 0, ans := 0
- สำหรับ l ในช่วง 1 ถึง n-2:
- r := max(r, l+1)
- while r < n-1 และ ss[r] - ss[l] < ss[l]: r := r + 1
- rr := max(rr, r)
- while rr < n-1 และ ss[n] - ss[rr+1] >= ss[rr+1] - ss[l]: rr := rr + 1
- ถ้า ss[l] > ss[r] - ss[l]: ออกจากลูป
- ถ้า ss[r] - ss[l] > ss[n] - ss[r]: ข้ามรอบถัดไป
- ans := (ans + rr - r + 1) mod m
- return ans
ตัวอย่าง
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))
อินพุต
[1,7,3,6,5]
เอาต์พุต
3
