Program to find sum of contiguous sublist with maximum sum in Python

Question

Program to find sum of contiguous sublist with maximum sum in Python

PythonServer Side ProgrammingProgramming

---

---

Suppose we have an array A. We have to find the contiguous sublist which has the maximum sum, and also return its sum. So if the array A is like A = [-2,1,-3,4,-1,2,1,-5,4], then the sum will be 6. And the subarray will be [4, -1, 2, 1].

To solve this we will try to use Dynamic programming approach.

• define an array dp same as the size of A, and fill it with 0

• dp[0] := A[0]

• for i := 1 to size of A – 1

  • dp[i] := maximum of dp[i – 1] + A[i] and A[i]

• return max in dp

Let us see the following implementation to get better understanding −

Example

Live Demo

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))

Input

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

Output

8

Arnab Chakraborty

Published on 09-Oct-2020 18:37:01

Previous Page Print Page

Next Page  

Advertisements