Program to find maximum sum of two non-overlapping sublists in Python

Suppose we have a list of numbers called nums and two values x and y, we have to find the maximum sum of two non-overlapping sublists in nums which have lengths x and y.

So, if the input is like nums = [3, 2, 10, -2, 7, 6] x = 3 y = 1, then the output will be 22, as the sublist with length 3 we select [3, 2, 10] and for the other we select [7].

To solve this, we will follow these steps −

• P := a list with single element 0
• for each x in A, do
  • insert (last element of P + x) at the end of P
• Define a function solve() . This will take len1, len2
• Q := a list with element (P[i + len1] - P[i]) for each i in range 0 to size of P - len1
• prefix := a copy of Q
• for i in range 0 to size of prefix - 1, do
  • prefix[i + 1] := maximum of prefix[i + 1] and prefix[i]
• ans := -infinity
• for i in range len1 to size of P - len2, do
  • left := prefix[i - len1]
  • right := P[i + len2] - P[i]
  • ans := maximum of ans and (left + right)
• return ans
• From the main method do the following −
• return maximum of solve(len1, len2) , solve(len2, len1)

Let us see the following implementation to get better understanding −

Example

 Live Demo

class Solution:    def solve(self, A, len1, len2):       P = [0]       for x in A:          P.append(P[-1] + x)       def solve(len1, len2):          Q = [P[i + len1] - P[i] for i in range(len(P) - len1)]          prefix = Q[:]          for i in range(len(prefix) - 1):             prefix[i + 1] = max(prefix[i + 1], prefix[i])             ans = float("-inf")             for i in range(len1, len(P) - len2):                left = prefix[i - len1]                right = P[i + len2] - P[i]             ans = max(ans, left + right)             return ans          return max(solve(len1, len2), solve(len2, len1)) ob = Solution() nums = [3, 2, 10, -2, 7, 6] x = 3 y = 1 print(ob.solve(nums, x, y))

Input

[3, 2, 10, -2, 7, 6], 3, 1

Output

22