企业官网建设流程全解析

建一个公司网站,郑州网站建设模板制作,成品网站货源1688在线,贵阳网站定制电话号码题目与常规 Kadane 回顾 题目#xff1a; 给定一个「环形」整数数组 nums#xff0c;要求返回一个非空连续子数组的最大和。leetcode 如果数组不是环而是直线#xff0c;这就是经典的「最大子数组和」问题#xff0c;可以直接用 Kadane 算法解决#xff1a; 维护当前前…题目与常规 Kadane 回顾题目给定一个「环形」整数数组 nums要求返回一个非空连续子数组的最大和。leetcode如果数组不是环而是直线这就是经典的「最大子数组和」问题可以直接用Kadane 算法解决维护当前前缀最优curMax到当前位置为止、必须以当前元素结尾的最大和。转移curMax max(nums[i], curMax nums[i])。同时更新全局答案maxSub max(maxSub, curMax)。这一套可以得到「不回环」情况下的最大子数组和。环形数组的关键拆分思路环形的麻烦在于子数组可以「跨尾到头」例如[5, -3, 5]的最优子数组是[5, 5]中间的-3被跳过。关键观察环形最大子数组只有两种形态不回环像普通数组那样在中间某一段上完全不跨越尾和头。对应答案就是经典 Kadane 的maxSub。回环形态类似「尾巴一段 头部一段」中间有一段连续区间被挖掉不选。把数组想象成一圈选中的一整圈减去中间没选的那一段 回环子数组。如果记数组总和为total中间那段是一个「连续子数组」它的和记为minSub则回环子数组和 total - minSub。所以不回环答案maxSub普通最大子数组和回环答案total - minSub总和减去最小子数组和最终答案应该是两者的较大值ans max ⁡ ( maxSub , total − minSub ) \text{ans} \max(\text{maxSub},\, \text{total} - \text{minSub})ansmax(maxSub,total−minSub)为什么要用「总和 - 最小子数组」用示例nums [5, -3, 5]直观理解数组总和t o t a l 5 ( − 3 ) 5 7 total 5 (-3) 5 7total5(−3)57所有连续子数组中和最小的是[-3]所以minSub -3。把[-3]这段挖掉其余部分是[5]尾部加上[5]头部组成回环子数组[5, 5]。用公式t o t a l − m i n S u b 7 − ( − 3 ) 10 total - minSub 7 - (-3) 10total−minSub7−(−3)10正好就是[5, 5]的和。这个思路的本质回环子数组 整个环 - 某一段连续区间。想让留下来的和最大就要让被挖掉那一段的和尽量小于是变成「最小子数组和」问题。最小子数组和同样可以用一个“反向 Kadane”求出来只是把max换成mincurMin min(nums[i], curMin nums[i])minSub min(minSub, curMin)。全负数的坑为什么这时只能用 maxSub看nums [-3, -2, -3]这个例子Kadane 最大子数组和最佳选择是[-2]所以maxSub -2。数组总和t o t a l − 3 ( − 2 ) ( − 3 ) − 8 total -3 (-2) (-3) -8total−3(−2)(−3)−8最小子数组和在全负数组上求“最小子数组和”的 Kadane 会把整段都选上得到minSub -8而且此时minSub total。代入回环公式t o t a l − m i n S u b − 8 − ( − 8 ) 0 total - minSub -8 - (-8) 0total−minSub−8−(−8)0问题来了这个0表面上看比maxSub -2大但它代表的含义是「把整段都当成中间被挖掉的最小子数组剩下的部分为空」——即根本没选任何元素。但题目要求子数组必须非空所以total - minSub在这种情况下其实是非法结果。因此对于「最小子数组就是整个数组」的情况minSub total只能认为“没有合法的回环方案”只能依赖不回环的maxSub。这就是常见代码里的特判if (minSub total) // 最小子数组等于整段 全负或等价情况 return maxSub; else return max(maxSub, total - minSub);这样就避免了选「空子数组」的假结果。一次遍历实现整体算法整体算法可以在一次循环中完成同时维护最大子数组、最小子数组和总和。核心变量设计curMax到当前下标、必须以当前元素结尾的最大子数组和。maxSub全局最大子数组和不回环。curMin到当前下标、必须以当前元素结尾的最小子数组和。minSub全局最小子数组和。total数组总和。每轮迭代curMax max(nums[i], curMax nums[i])maxSub max(maxSub, curMax)。curMin min(nums[i], curMin nums[i])minSub min(minSub, curMin)。total nums[i]。循环结束后如果minSub total说明最小子数组等于整段只能返回maxSub。否则返回max(maxSub, total - minSub)。时间复杂度 O(n)、空间 O(1)同时处理了只在中间的一段不回环从尾到头跨越的一段回环全负数等特殊情况。思路要点小结不必在环上「拼成 2n 数组 枚举起点」那样要么 O(n²)要么需要复杂的长度约束不适合这题。环形最大子数组拆成两种模式不回环用 Kadane 求maxSub回环用total - minSub。用「全负数时minSub total」这个条件判断是否存在合法的回环方案如果不存在就只能选最大单个元素也就是maxSub。整题的本质就是在环上做 Kadane 的最佳方式是同时维护「最大子数组」和「最小子数组」并用「总和减最小」来间接表示回环情况。