@zrythpzhl Thanks for posting your solution.. I have a question on 'valid' method.

Shouldn't we check for 'count==m' (i.e exactly m Split) at the last 'return' statement.
Otherwise we will return true even if the split is < m. is that fine ?

[7,2,-5,-10,8]
if(t<=dp[i])
dp[i]=t;
//else
// break;
Comment out the above two lines, you'll get the correct result. The two lines assume the number to be positive.

@fming Yes, I should like to have given out more explanation, but others later on posted a topic with very detailed explanation about this binary search solution, so just take a look at that :)

@souptikji Without the "continuous" I think it would be NP-hard. So then probably the limits would need to be lower, and what I'd do would depend on those limits.

You should precompute the partial sum instead of sum the subarray every time.
You should use binary search in the inner loop since the monotonics of dp(i, m - 1) and sum(i, j)
Here's the code
class Solution(object):
def splitArray(self, nums, m):
sums = [0]
for x in nums: sums.append(sums[-1] + x)
def dp(nums, j, m, cache):
if m == 1: return sums[j]
state = (j, m)
if state in cache: return cache[state]
res = 0x7fffffff
l, r = m - 1, j
while r - l > 1:
mid = l + (r - l) / 2
lval, rval = dp(nums, mid, m - 1, cache), sums[j] - sums[mid]
if lval < rval:
l = mid
else:
r = mid
res = min(res, lval)
res = min(res, max(dp(nums, l, m - 1, cache), sums[j] - sums[l]))
cache[state] = res
return res
cache = {}
res = dp(nums, len(nums), m, cache)
return res