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

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

उदाहरण के लिए, यदि इनपुट array = [4, 1, -2, -1] है, तो आउटपुट 17 होगा।

यदि हम array[0] के मान को उसके वर्ग मान से बदलते हैं, तो ऐरे [16, 1, -2, -1] बन जाता है। इससे संभव अधिकतम सबएरे [16, 1] है, और इसका अधिकतम योग मान 16 + 1 = 17 है।

हल करने के चरण

1. dp1 := float('-inf') मान वाली नई सूची
2. dp2 := float('-inf') मान वाली नई सूची
3. array में प्रत्येक num के लिए:
   • max(dp1[-1] + num, num) को dp1 के अंत में जोड़ें
   • max(dp1[-2] + num**2, num**2, dp2[-1] + num) को dp2 के अंत में जोड़ें
4. 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]

आउटपुट

17