分割数组的最大值

相关知识点

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