Python program to split an array to find the largest sum

This is a Leetcode problem –

Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.

Note –

If n is the length of the array, assume the following constraints are satisfied:

  • 1 ≤ n ≤ 1000
  • 1 ≤ m ≤ min(50, n)

Here is my first solution to this challenge (in Python) –

#Uses dynamic programming  import sys def split_array(nums, m):     """     :type nums: List[int]     :type m: int     :rtype: int     """     dp = [[sys.maxsize]*(m) for _ in range(len(nums)+1)]     acc = 0     dp[0][0] = 0     for i in range(1, len(nums)+1):         acc += nums[i - 1]         dp[i][0] = acc      for j in range(m):         dp[0][j] = 0      for i in range(1, len(nums)+1):         for i_ in range(i):             for j in range(1, m):                 dp[i][j] = min(dp[i][j], max(dp[i_][j-1], dp[i][0]-dp[i_][0]))     return dp[len(nums)][m-1] 

Here is my second solution to this challenge –

#Brute force   class Solution(object):     def __init__(self, nums, m):             self.nums = nums             self.m = m     def helper(self, nums, m):         if nums == []:             return 0         elif m == 1:             return sum(nums)         else:             min_result = float('inf')             for j in range(1,len(nums)+1):                 left, right = sum(nums[:j]), self.helper(nums[j:], m-1)                 min_result = min(min_result, max(left, right))             return min_result      def split_array_2(self, nums, m):          """         :type nums: List[int]         :type m: int         :rtype: int         """         return self.helper(nums, m) 

Both have the same outputs –

print(split_array([7,2,5,10,8], 2)) >>> 18  output = Solution([7,2,5,10,8], 2) print(output.split_array_2([7,2,5,10,8], 2)) >>> 18 

Explanation –

There are four ways to split nums into two subarrays. The best way is to split it into [7,2,5] and[10,8], where the largest sum among the two subarrays is only 18.


Overall, I would like to have a code review for the efficiency of both the programs and would like to know if I could make any of these programs shorter (and more efficient). Any alternatives are welcome.

Any help would be highly appreciated.