C++ DP SOLUTION


  • 1
    S
    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];
        }
    };
    

  • 0
    S

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


  • 0

    @singku
    Elegant Solution in Dynamic Programming


  • 0
    A

    @singku Your early termination will not work on negative inputs


Log in to reply
 

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