class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        int len = nums.size(), sum = 0;
        //dp[i][j] represents minimum largest sum by dividing first i characters into j subarrays
        //dp[i][j] = min(max(dp[k][j - 1], sum(k + 1, i)))
        //base case: dp[i][1] = presum[i] - 0(since we need to get dp[k][j - 1] when calculate dp[i][j]), dp[i][0] = INT_MAX, dp[0][i] = INT_MAX;
        vector<vector<int>> dp(len + 1, vector<int>(m + 1, INT_MAX));
        vector<int> preSums(1, 0);
        for(auto& num : nums){sum += num;preSums.push_back(sum);};
        for(int i = 0; i < len; ++i)
        {
            dp[i + 1][1] = preSums[i + 1] - preSums[0];
            for(int j = 2; j <= min(i + 1, m); ++j)
            {
                for(int k = i; k >= j - 1; --k)
                {
                    dp[i + 1][j] = min(max(dp[k][j - 1], preSums[i + 1] - preSums[k]), dp[i + 1][j]);
                }
            }
        }
        return dp[len][m];
    }
};