# 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.