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`

≤ 10001 ≤`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.