โปรแกรมค้นหาวิธีแยกอาร์เรย์ออกเป็นสามอาร์เรย์ย่อยใน Python

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

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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