分割数组的最大值
相关知识点
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例：付视频课程
二分 过些天整理基础知识
题目
给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。
设计一个算法使得这 m 个子数组各自和的最大值最小。
示例 1：
输入：nums = [7,2,5,10,8], m = 2
输出：18
解释：
一共有四种方法将 nums 分割为 2 个子数组。
其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
示例 2：
输入：nums = [1,2,3,4,5], m = 2
输出：9
示例 3：
输入：nums = [1,4,4], m = 3
输出：4
提示：
1 <= nums.length <= 1000
0 <= nums[i] <= 10^6
1 <= m <= min(50, nums.length)
解法一：暴力解法
时间复杂度O(nnm)，n是nums的长度。vMaxSum共有m*n种状态，求每种状态需的时间复杂度是O(n)。vPreSum记录前缀和，vMaxSum[i][j] 记录将nums[0,j]分成i个子数组的最大和。j’取值范围[0,j)，vMaxSum[i][j]就是所有max(vMaxSum[i-1][j’],vPreSum[j+1] - vPreSum[j’])的最小值。这个时间复杂度在通过和不通过的边缘。
解法二：滑动窗口
假定j的j1是x，则当j增加时，x不变或增加。 当j++，vMaxSum[i-1][j’]不变，vPreSum[j+1] - vPreSum[j’] 增加。下面用因果表来证明。令L(j,x)= vMaxSum[i-1][x] R(j,x) = vPreSum[j+1] - vPreSum[x] |。
如果L(j,x)<= R(j,x)。x减少后，左式减少或不变，右式增加或不变。i++后，右式变大或不变。所以x减少只会让右式变大或不变。而右式显然大于左式，所以减少左式不会减少最大值。
| 规章编号 | 因 | 证明 | 果 |
| 假设一 | 合适的j1就是x | ||
| 假设二 | L(j,x)> R(j,x) | ||
| 推论一 | 假设一 假设二 | x–后,L变小，R变大。如果L(j,x-1) >= R(j,x-1)，结合假设二，x-1比x更合适。与假设一矛盾。 | L(j,x-1) < R(j,x-1)] |
| 推论二 | 对于j+1,取x最大和为L(j,x)或R(j+1,x);取x-1，最大和为R(j+1,x-1) | ||
代码
class Solution { public: int splitArray(vector& nums, int k) { m_c = nums.size(); vector vPreSum(1); for (const auto& n : nums) { vPreSum.emplace_back(n + vPreSum.back()); } vector pre(m_c); for (int i = 0; i < m_c; i++) { pre[i] = vPreSum[i + 1] - vPreSum[0]; } for(int i = 1 ; i < k ; i++ ) { vector dp(m_c,-1); int k = i ; for (int j = i; j < m_c; j++) { k–; int iMax = INT_MAX; #define MaxCro (max(pre[k], vPreSum[j + 1] - vPreSum[k+1])) while ((k < j) && (MaxCro <= iMax)) { iMax = MaxCro; k++; } dp[j] = iMax; } pre.swap(dp); } return pre.back(); } int m_c; };
测试用例
template void Assert(const vector& v1, const vector& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { assert(v1[i] == v2[i]); } } template void Assert(const T& t1, const T& t2) { assert(t1 == t2); } int main() { vector nums = { 1,2,3,4,5,6 }; int k = 2; auto res = Solution().splitArray(nums, k); Assert(res, 11);
nums = { 1, 0, 3, 3, 0, 6 }; k = 2; res = Solution().splitArray(nums, k); Assert(res, 7); nums = { 6,5,3,2,2,1 }; k = 5; res = Solution().splitArray(nums, k); Assert(res, 6); nums = { 1,0,3,3,0,1 }; k = 5; res = Solution().splitArray(nums, k); Assert(res, 3); //CConsole::Out(res);
}
2023年一月版：二分
class Solution { public: int splitArray(vector& nums, int k) { int iMax = *std::max_element(nums.begin(), nums.end()); int iSum = std::accumulate(nums.begin(), nums.end(),0);
int left = iMax-1, right = iSum; while (left+1 < right) { int iMid = (left + right) / 2; if (NeedK(nums, iMid) <= k) { right = iMid; } else { left = iMid; } } return right; } int NeedK(const vector<int>& nums, int iMaxSum) { int iNeedK = 1; int iSum = 0; for (const auto& n : nums) { if (iSum + n > iMaxSum) { iSum = n; iNeedK++; } else { iSum+=n; } } return iNeedK; }
};
2023年8月版也是二分
class Solution { public: int splitArray(vector& nums, int k) { int iSum = std::accumulate(nums.begin(), nums.end(), 0); int left = -1, r = iSum; while (r > left + 1) { const auto mid = left + (r - left) / 2; if (Is(nums, mid, k)) { r = mid; } else { left = mid; } } return r; } bool Is(const vector& nums, const int iMaxSum, int k) { k–;//可以分配的新组 int iHas = 0; for (const auto& n : nums) { iHas += n; if (iHas > iMaxSum) { k–; iHas = n; if (n > iMaxSum) { return false; } } } return k >= 0; } };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 鄙人想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 墨家名称的来源：有所得以墨记之。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
