//algorithm 1: dpconst int maxn = 1005;const int maxm = 55;int d[maxn][maxm];class Solution {public: int splitArray(vector<int>& nums, int m) { int n = nums.size(); if (n == 0) return 0; int S[maxn]; S[0] = nums[0]; for (int i = 1; i < n; i++) S[i] = S[i - 1] + nums[i]; for (int i = 0; i < n; i++) d[i][1] = S[i]; for (int j = 2; j <= m; j++) { for (int i = 0; i < n; i++) { d[i][j] = INT_MAX; for (int k = 0; k < i; k++) d[i][j] = min(d[i][j], max(d[k][j - 1], S[i] - S[k])); } } return d[n - 1][m]; }};//algorithm 2: Binary Searchclass Solution {public: bool judge(long long x, int m, vector<int> nums) { int cnt = 0; bool f = false; long long sum = 0; for (int i = 0; i < nums.size(); i++) { if ((long long)nums[i] > x) return false; sum += nums[i]; if (i == nums.size() - 1) { if (sum > x) cnt += 2; else cnt++; } else { if (sum > x) { cnt++; sum = nums[i]; } } } if (cnt > m) return false; return true; } int splitArray(vector<int>& nums, int m) { int n = nums.size(); if (n == 0) return 0; long long sum = nums[0], MIN = nums[0]; for (int i = 1; i < n; i++) {sum += nums[i]; MIN = min(MIN, (long long)nums[i]);} long long L = MIN, R = sum, M = L + (R - L) / 2, res = sum; while (L < R) { if (R == L + 1) { if (judge(L, m, nums)) M = L; else M = R; break; } M = L + (R - L) / 2; if (judge(M, m, nums)) R = M; else L = M; } return M; }};
