# C++ DP SOLUTION

• ``````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[i-1] + nums[i]);
}
// build dp from 0 to n-1 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 i-1; i-1, i-2...; i-1, i-2..k-1;
for (int j = i; j >= k-1; j--) {//0..k-2 can be divided to mostly k-1 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[j-1][k-1]));
}
}
}
return dp[n-1][m];
}
};
``````

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

• @singku
Elegant Solution in Dynamic Programming

• @singku Your early termination will not work on negative inputs

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