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

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