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减少只会让右式变大或不变。而右式显然大于左式，所以减少左式不会减少最大值。

代码

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;
 }
 };

扩展阅读

相关下载

想高屋建瓴的学习算法，请下载《闻缺陷则喜算法册》doc版

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17