पायथन में एक ऑपरेशन के बाद अधिकतम सबअरे का योग जानने का कार्यक्रम

मान लीजिए, हमें पूर्णांक संख्याओं वाली एक सरणी दी गई है। हम एक ऑपरेशन कर सकते हैं जहां हम array[i] के मान को उसके चुकता मान से बदल सकते हैं; या सरणी [i] * सरणी [i]। इस तरह के केवल एक ऑपरेशन की अनुमति है और हमें ऑपरेशन के बाद अधिकतम संभव सबअरे का योग वापस करना होगा। उपसरणी खाली नहीं हो सकती।

इसलिए, अगर इनपुट ऐरे =[4, 1, -2, -1] जैसा है, तो आउटपुट 17 होगा।

यदि हम सरणी [0] में मान को उसके चुकता मान से प्रतिस्थापित करते हैं, तो सरणी [16, 1, -2, -1] बन जाती है। इससे संभव अधिकतम उप-सरणी [16, 1] है, और इसका अधिकतम योग मान 16 + 1 =17 है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

dp1 :=एक नई सूची जिसमें मान ऋणात्मक अनंत है
dp2 :=एक नई सूची जिसमें मान ऋणात्मक अनंत है
सरणी में प्रत्येक अंक के लिए, करें
- dp1 के अंत में अधिकतम ((dp1 + num का अंतिम तत्व), num) डालें
- dp2 के अंत में अधिकतम ((dp1 + num^2 का दूसरा अंतिम तत्व), num^2, (dp2 + num का अंतिम तत्व)) डालें
dp2 का अधिकतम तत्व लौटाएं

उदाहरण

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

def solve(array):
   dp1 = [float('-inf')]
   dp2 = [float('-inf')]
   for num in array:
      dp1.append(max(dp1[-1] + num, num))
      dp2.append(max(dp1[-2] + num**2, num**2, dp2[-1]+num))
   return max(dp2)

print(solve([4, 1, -2, -1]))

इनपुट

[4, 1, -2, -1]