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

মনে করুন nums নামক একটি অ্যারে আছে। আমাদের এই অ্যারেটি তিনটি নন-এম্পটি কনটিগুয়াস সাবঅ্যারেতে ভাগ করার 'ভালো' উপায়ের সংখ্যা বের করতে হবে। উত্তর বড় হলে 10^9 + 7 দিয়ে মডুলো রিটার্ন করুন। এখানে একটি ভাগ 'ভালো' হবে যদি অ্যারেটি বাম থেকে ডানে তিনটি নন-এম্পটি সাবঅ্যারেতে ভাগ করা যায় এবং বাম পার্টের যোগফল মাঝপার্টের যোগফলের চেয়ে কম বা সমান হয়, এবং মাঝপার্টের যোগফল ডান পার্টের যোগফলের চেয়ে কম বা সমান হয়।

যেমন, ইনপুট nums = [2,3,3,3,7,1] হলে, আউটপুট হবে ৩ কারণ তিনটি ভিন্ন ভাগ করার উপায়:

[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 := 0 দিয়ে (1+n) সাইজের একটি অ্যারে
nums-এ থাকা প্রতিটি index i এবং value val-এর জন্য
- ss[i] := ss[i-1] + val
r := 0, rr := 0, ans := 0
l = 1 থেকে n-2 পর্যন্ত
- r := max(r, l+1)
- যখন r < n-1 এবং ss[r] - ss[l] < ss[l], तब
  - r := r + 1
- rr := max(rr, r)
- যখন 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
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]