1251. Split Array Largest Sum - double check

Binary search
int splitArray(vector<int>& nums, int m) { long long left = 0, right = 0; for (int i = 0; i < nums.size(); ++i) { left = max((int)left, nums[i]); right += nums[i]; } while (left < right) { long long mid = left + (right - left) / 2; if (can_split(nums, m, mid)) right = mid; else left = mid + 1; } return left; } bool can_split(vector<int>& nums, int m, int sum) { int cnt = 1, curSum = 0; for (int i = 0; i < nums.size(); ++i) { curSum += nums[i]; if (curSum > sum) { curSum = nums[i]; ++cnt; if (cnt > m) return false; } } return true; }

DP
int splitArray(vector<int> &nums, int m) { // write your code here int n = nums.size(); vector<int> sums(n + 1, 0); vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX)); dp[0][0] = 0; for (int i = 1; i <= n; ++i) { sums[i] = sums[i - 1] + nums[i - 1]; } for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { for (int k = i - 1; k < j; ++k) { int val = max(dp[i - 1][k], sums[j] - sums[k]); dp[i][j] = min(dp[i][j], val); } } } return dp[m][n]; }