class Solution {
public:
int splitArray(vector<int>& nums, int m) {
int n = nums.size();
//dp[i][k] means max sum of k parts of elements 0..i
vector<vector<long>> dp(n, vector<long>(m+1, INT_MAX));
//sum array is used to calculate range sum of i..j
vector<long> sum(n, 0);
for (int i = 0; i < n; i++) {
sum[i] = i == 0 ?nums[0] :(sum[i1] + nums[i]);
}
// build dp from 0 to n1 emelents
for (int i = 0; i < nums.size(); i++) {
//elements from 0 to indexi can be divided to i+1 parts mostly;
int maxDivide = min(m, i+1);
//for each dividing choice
for (int k = 1; k <= maxDivide; k++) {
if (k == 1) {
dp[i][k] = sum[i];
continue;
}
//divide 0..i to k parts, so i can be with i1; i1, i2...; i1, i2..k1;
for (int j = i; j >= k1; j) {//0..k2 can be divided to mostly k1 parts
long partsum = sum[i]  sum[j] + nums[j];
if (partsum > dp[i][k]) break; //early termination
dp[i][k] = min(dp[i][k], max(partsum, dp[j1][k1]));
}
}
}
return dp[n1][m];
}
};
C++ DP SOLUTION


@singku DP method can be extended to problem where restriction of positive integers is removed.

