पायथन में सकारात्मक गुणनफल वाले सबएरे की अधिकतम लंबाई खोजने का प्रोग्राम

मान लीजिए हमारे पास nums नामक एक सरणी है, हमें उस सबएरे की अधिकतम लंबाई ज्ञात करनी है जहां उसके सभी तत्वों का गुणनफल सकारात्मक हो। हमें सकारात्मक गुणनफल वाले सबएरे की अधिकतम लंबाई ज्ञात करनी है।

उदाहरण के लिए, यदि इनपुट है nums = [2,-2,-4,5,-3], तो आउटपुट 4 होगा क्योंकि पहले चार तत्व एक ऐसा सबएरे बनाते हैं जिसका गुणनफल सकारात्मक है।

समाधान दृष्टिकोण

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

• एक फ़ंक्शन util() परिभाषित करें। यह s, e लेगा
• neg := 0
• ns := -1, ne := -1
• i को s से e तक रेंज में लिए:
  • यदि nums[i] < 0, तो:
    • neg := neg + 1
    • यदि ns == -1, तो ns := i
    • ne := i
• यदि neg सम है, तो:
  • e-s+1 लौटाएं
• अन्यथा:
  • max(e-ns, ne-s) लौटाएं
• मुख्य विधि से:
  • ans := 0
  • s := -1, e := -1
  • i को 0 से nums के आकार तक रेंज में लिए:
    • यदि nums[i] != 0 और s == -1, तो s := i
    • अन्यथा यदि nums[i] == 0 और s != -1, तो:
      • e := i-1
      • ans := max(ans, util(s, e))
      • s := -1, e := -1
  • यदि s != -1 और e == -1, तो:
    • e := nums का आकार - 1
    • ans := max(ans, util(s, e))
  • ans लौटाएं

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

def util(s, e):
    neg = 0
    ns, ne = -1, -1
    for i in range(s, e+1):
        if nums[i] < 0:
            neg += 1
            if ns == -1:
                ns = i
            ne = i
    if neg == 0 or neg % 2 == 0:
        return e - s + 1
    else:
        return max(e - ns, ne - s)

def solve(nums):
    ans = 0
    s, e = -1, -1
    for i in range(len(nums)):
        if nums[i] != 0 and s == -1:
            s = i
        elif nums[i] == 0 and s != -1:
            e = i - 1
            ans = max(ans, util(s, e))
            s = -1
            e = -1
    if s != -1 and e == -1:
        e = len(nums) - 1
        ans = max(ans, util(s, e))
    return ans

nums = [2, -2, -4, 5, -3]
print(solve(nums))

इनपुट

[2,-2,-4,5,-3]

आउटपुट

4