# DP O(nm) Solution

• The O(n^2m) DP solution to this problem is pretty obvious, where the transition function can be written as
`dp[i][j] = min{max{dp[k][j-1], subsum(k+1, i)}}, 0 <= k < i`
where `dp[i][j]` is the optimal result for splitting `nums[:i+1]` into `j` subarrays. And then for each i, j you would require O(n) time to find the k that minimizes `dp[i][j]`, which makes this an overall O(n^2m) algorithm..

The key to reducing time complexity down to O(nm) is the monotonic properties that `dp` and `subsum` hold. Mathematically I found myself hard to explain this well, but intuitively, if the last subarray for `dp[i][j]` is `nums[k], nums[k+1], ..., nums[i]`, then for `dp[i][j+1]` the last subarray would always be some `nums[k+x], ..., nums[i], x>=0`, because if you were cutting an array evenly into `j + 1` continuous subarray, the last subarray would always be smaller than it would had been using one less cut. So every time you find a `k` that minimizes `dp[i][j]` you only need to consider subarray starting from or after `k` when computing `dp[i][j+1]`.

``````class Solution(object):
def splitArray(self, nums, m):
n = len(nums)
if not n:
return 0
pre_sum = [0] * (n + 1)
for i in range(n):
pre_sum[i + 1] = pre_sum[i] + nums[i]
sub_sum = lambda i, j: pre_sum[j + 1] - pre_sum[i]

dp = [[0 for _ in range(m + 1)] for _ in range(n)]
for i in range(n):
dp[i][1] = pre_sum[i + 1]
k = 0
for j in range(2, min(m + 1, i + 2)):
while k < i - 1 and max(dp[k][j-1], sub_sum(k+1, i)) > max(dp[k+1][j-1], sub_sum(k+2,i)):
k += 1
dp[i][j] = max(dp[k][j - 1], sub_sum(k+1, i))
return dp[n - 1][m]

``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.