পাইথনে অ্যারেকে তিনটি সাবয়ারেতে বিভক্ত করার উপায় খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের nums নামক একটি অ্যারে আছে, আমাদের এই অ্যারে সংখ্যাগুলিকে ভাগ করার জন্য ভাল উপায়গুলির সংখ্যা খুঁজে বের করতে হবে। উত্তরটি খুব বড় হতে পারে তাই ফলাফল মডিউল 10^9 + 7 প্রদান করুন। এখানে একটি অ্যারের একটি বিভাজন (পূর্ণসংখ্যা উপাদান সহ) ভাল যদি অ্যারেটি বাম থেকে ডানে যথাক্রমে তিনটি অ-খালি সংলগ্ন সাব্যারেতে বিভক্ত হয় এবং এর সমষ্টি বাম দিকের উপাদানগুলি মধ্য অংশের উপাদানগুলির যোগফলের থেকে কম বা সমান এবং মধ্য অংশের উপাদানগুলির যোগফল ডানদিকের উপাদানগুলির সমষ্টির থেকে কম বা সমান৷

সুতরাং, যদি ইনপুটটি সংখ্যার মত হয় =[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 :=সংখ্যার আকার,
• m :=10^9+7
• ss :=আকারের একটি অ্যারে (1+n) এবং 0 দিয়ে পূরণ করুন
• প্রতিটি সূচক i এবং মান val এর জন্য সংখ্যায় , করুন
  • ss[i] :=ss[i-1] + val
• r :=0, rr :=0, উত্তর :=0
1 থেকে n-2 রেঞ্জের l-এর জন্য
• করুন
  • r :=সর্বাধিক r এবং l+1
  • যখন r
  • r :=r + 1
• rr :=rr এবং r এর সর্বোচ্চ
• যখন rr =ss[rr+1] - ss[l], do
  • rr :=rr + 1
• যদি ss[l]> ss[r] - ss[l] হয়, তাহলে
  • লুপ থেকে বেরিয়ে আসুন
• যদি ss[r] - ss[l]> ss[n] - ss[r] হয়, তাহলে
  • পরবর্তী পুনরাবৃত্তির জন্য যান
• উত্তর :=(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