甘肃购物网站建设,网站服务器租用合同,网络爬虫需要自己做网站吗,电商营销推广方案分割数组的最大值
相关知识点
C算法#xff1a;前缀和、前缀乘积、前缀异或的原理、源码及测试用例#xff1a;付视频课程
二分 过些天整理基础知识
题目
给定一个非负整数数组 nums 和一个整数 m #xff0c;你需要将这个数组分成 m 个非空的连续子数组。 设计一个算法…分割数组的最大值
相关知识点
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[j1] - vPreSum[j’])的最小值。这个时间复杂度在通过和不通过的边缘。
解法二滑动窗口
假定j的j1是x则当j增加时x不变或增加。 当jvMaxSum[i-1][j’]不变vPreSum[j1] - vPreSum[j’] 增加。下面用因果表来证明。令L(j,x) vMaxSum[i-1][x] R(j,x) vPreSum[j1] - 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)]推论二对于j1,取x最大和为L(j,x)或R(j1,x);取x-1最大和为R(j1,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[k1])) 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 (left1 right){int iMid (left right) / 2;if (NeedK(nums, iMid) k){right iMid;}else{left iMid;}}return right;}int NeedK(const vectorint nums, int iMaxSum){int iNeedK 1;int iSum 0;for (const auto n : nums){if (iSum n iMaxSum){iSum n;iNeedK;}else{iSumn;}}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 C17 或者 操作系统win10 开发环境 VS2022 C17
