पायथन में सरणी को तीन उप-सरणी में विभाजित करने के तरीकों की संख्या खोजने का कार्यक्रम

मान लीजिए कि हमारे पास अंक नामक एक सरणी है, हमें इस सरणी संख्याओं को विभाजित करने के अच्छे तरीकों की संख्या ज्ञात करनी है। उत्तर बहुत बड़ा हो सकता है इसलिए रिटर्न परिणाम मॉड्यूलो 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 :=अंकों का आकार,
म :=10^9+7
ss :=आकार की एक सरणी (1+n) और 0 से भरें
प्रत्येक इंडेक्स के लिए i और वैल्यू वैल्यू इन nums , do
- ss[i] :=ss[i-1] + वैल
r :=0, rr :=0, ans :=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) मॉड 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]