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

मान लीजिए हमारे पास एक सरणी A है। हमें वह सन्निकट सबलिस्ट ढूंढनी है जिसका अधिकतम योग हो, और उसका योग भी लौटाना है। उदाहरण के लिए, यदि A = [-2,1,-3,4,-1,2,1,-5,4], तो योग 6 होगा। और सबअरे [4, -1, 2, 1] होगा।

इसे हल करने के लिए हम डायनामिक प्रोग्रामिंग दृष्टिकोण का उपयोग करेंगे।

• dp सरणी A के आकार की बनाएं और 0 से भरें।

• dp[0] := A[0]।

• i को 1 से len(A)-1 तक:

  • dp[i] := max(dp[i-1] + A[i], A[i])।

• max(dp) लौटाएं।

उदाहरण

class Solution(object):    def solve(self, nums):       dp = [0 for i in range(len(nums))]       dp[0] = nums[0]       for i in range(1,len(nums)):          dp[i] = max(dp[i-1]+nums[i],nums[i])       return max(dp) nums = [-2,1,-3,7,-2,2,1,-5,4] ob1 = Solution() print(ob1.solve(nums))

इनपुट

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

आउटपुट

8