湖州建设局网站 项目验收流程,wordpress 栏目标题,广告推广系统,建设项目管理公司网站本文涉及知识点
C算法#xff1a;前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 单调双队列 贪心
题目
给你一个下标从 0 开始的整数数组 nums 。 你可以执行任意次操作。每次操作中#xff0c;你需要选择一个 子数组 #xff0c;并将这个子数组用它所…本文涉及知识点
C算法前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 单调双队列 贪心
题目
给你一个下标从 0 开始的整数数组 nums 。 你可以执行任意次操作。每次操作中你需要选择一个 子数组 并将这个子数组用它所包含元素的 和 替换。比方说给定数组是 [1,3,5,6] 你可以选择子数组 [3,5] 用子数组的和 8 替换掉子数组然后数组会变为 [1,8,6] 。 请你返回执行任意次操作以后可以得到的 最长非递减 数组的长度。 子数组 指的是一个数组中一段连续 非空 的元素序列。 示例 1 输入nums [5,2,2] 输出1 解释这个长度为 3 的数组不是非递减的。 我们有 2 种方案使数组长度为 2 。 第一种选择子数组 [2,2] 对数组执行操作后得到 [5,4] 。 第二种选择子数组 [5,2] 对数组执行操作后得到 [7,2] 。 这两种方案中数组最后都不是 非递减 的所以不是可行的答案。 如果我们选择子数组 [5,2,2] 并将它替换为 [9] 数组变成非递减的。 所以答案为 1 。 示例 2 输入nums [1,2,3,4] 输出4 解释数组已经是非递减的。所以答案为 4 。 示例 3 输入nums [4,3,2,6] 输出3 解释将 [3,2] 替换为 [5] 得到数组 [4,5,6] 它是非递减的。 最大可能的答案为 3 。 参数范围 1 nums.length 105 1 nums[i] 105
枚举最后一个子数组nums(j,i]
假定结果向量为vRet nums[0,j] 需要记录两个子状态最有一个子数组的和vRet的长度操作前的子数组数量。枚举这些状态时间复杂度O(n)枚举i时间复杂度O(n)枚举j时间复杂度O(n)。故总时间复杂度o(n3)。合并nums[0,j]和nums(j,i]有两种操作 操作一nums(j,i]全部合并到vRet[j]的最后一个元素。无前提条件。 操作二nums(j,i]成为新元素。前天条件nums(j,i]大于vRet[j]的最后一个元素。
贪心不存在len len2且v1 v2
令nums[0,i)合法分成n段最后一段的值为fin即分成一段最后的值为fi1分成两段最后的值为fi2。 令nums[0,j)…fjn。
证明对于任意数组子数组fxn 一定 大与等于fxn1。x是j,j等… n1: fx1 为整个数组的和fx2为数组第二部分的和。显然成立。 n 1 用反证法 假定可以合法分成n段分别为{a1,a2…an} 假定可以合法分成n1段:分别为(b1,b2…bn,bn1}。bn1可能有多个值取最小值 假定an bn1则{a1,a2,…an-1} 和大于{b1…bn}的和 假定前者包括nums[0,i)后者包括nums[0,j) i j 则{b1,b2…bnnums[j,i}是nums[0,i)的一个合法分成n段,{a1…an-1} 是nums[0,i)一个合法n-1段。
bnnums[j,i就是fin, an-1,就是fn-1 fxn-1 fnx an-1 bnnums[j,i) 因为an an-1 {b1,b2…bnnums[j,i),an} 是一个nums的n1段划分。 结合假设an bn1 和 bn1是最小值矛盾
优化后时间复杂度O(n)
如果nums[0,i)存在长度len则nums[0,i]一定存在长度为len的结果将nums[i]追加到最后。 判断nums[0,i]能否则在nums[0,j] 增加一个元素nums(j,i]的和需要判断 vPreSum[i1] - vPreSum[j1] Last[j] 即vPreSump[i1] Last[j]vPreSum[j1] Last[j] 是最后元素的值 Last[j]vPreSum[j1] 可以合并一个变量llPre。已知状态只需要保留最大长度长度相同保留llPre最小。 此解法错误还在摸索中。
class Solution {
public:int findMaximumLength(vectorint nums) {m_c nums.size();auto vPreSum CreatePreSum(nums);int len 0;long long llPre 0;int preIndex -1;for (int i 0; i m_c; i){if (vPreSum[i 1] llPre){len;llPre vPreSum[i1] (vPreSum[i 1] - vPreSum[preIndex 1]);preIndex i;}else{const long long curAdd vPreSum[i1] - vPreSum[preIndex1] (vPreSum[i 1] - vPreSum[preIndex 1]);if (curAdd 0){llPre curAdd;preIndex i;}}}return len;}int m_c;
};正确解法
下标从小到大遍历nums[i]queIndexs记录[0,i)淘汰以下 一j1 j2也就(j1,i]的和大于(j2,i]。也就是j1的最后一个数大于j2的最后一个数。llPre1 大于llPre2也就llPre1更难匹配淘汰j1。淘汰后下标升序 llPre 降序。 二j找到第一个i后淘汰。假定j的长度为len,i1 i2。i1可以选择{… (j,i1],(i1,i2]} 和{…{j,i2]}而i2只能选择后者所以i1不劣与i2。
注意如果无法长度1则vLast[i] vLast[i - 1] nums[i]
队首元素的长度和队尾元素的长度相差不会超过1
双向队列中的下标升序也就是长度升序。 假定新入队的长度是len则被淘汰的队首长度为len-1。由于是升序所以队中元素的长度都大于等于len-1小于等于len
templateclass T long long
vectorT CreatePreSum(const vectorint nums)
{vectorT preSum;preSum.push_back(0);for (int i 0; i nums.size(); i){preSum.push_back (preSum[i] nums[i]);}return preSum;
}class Solution {
public:int findMaximumLength(vectorint nums) {m_c nums.size();auto vPreSum CreatePreSum(nums);vectorint vRet(m_c,1),vLast(m_c,nums.front());std::dequeint queIndexs;queIndexs.emplace_back(0);auto Pre [](const int index) {return vPreSum[index 1] vLast[index]; };for (int i 1; i m_c; i){vRet[i] vRet[i - 1];vLast[i] vLast[i - 1] nums[i];while (queIndexs.size() (vPreSum[i 1] Pre(queIndexs.front()))){vRet[i] vRet[queIndexs.front()]1;vLast[i] vPreSum[i 1] - vPreSum[queIndexs.front() 1];queIndexs.pop_front();}while (queIndexs.size() (Pre(queIndexs.back()) Pre(i))){queIndexs.pop_back();}queIndexs.emplace_back(i);}return vRet.back();}int m_c;
};错误解法
class Solution { public: int findMaximumLength(vector nums) { stack sta; int i 0; while (i nums.size()) { long long cur 0; while (sta.size() (i nums.size()) (sta.top() cur nums[i])) { cur nums[i]; } if (i nums.size()) { break;//理论上需要栈顶的值由于我需要的是数量所以可以不修改 } sta.emplace(cur nums[i]); } return sta.size(); } }; 扩展阅读
视频课程
有效学习明确的目标 及时的反馈 拉伸区难度合适可以先学简单的课程请移步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 如无特殊说明本算法用C 实现。
