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]
```