滨州 网站建设,用.net做的网站,wordpress cdn插件,wordpress 插件开启使用“Kadane’s Algorithm”来解决。
Kadane’s Algorithm 在每个步骤中都保持着一个局部最优解#xff0c;即以当前元素为结尾的最大子数组和(也就是局部最优解)#xff0c;并通过比较这些局部最优解和当前的全局最优解来找到最终的全局最优解。
Kadane’s Algorithm的核…
使用“Kadane’s Algorithm”来解决。
Kadane’s Algorithm 在每个步骤中都保持着一个局部最优解即以当前元素为结尾的最大子数组和(也就是局部最优解)并通过比较这些局部最优解和当前的全局最优解来找到最终的全局最优解。
Kadane’s Algorithm的核心思想是在遍历数组的过程中动态地计算出以每个元素结尾的最大子数组和并用一个变量来记录出现过的最大值。简单来说它帮我们找到了一种巧妙的方式在一次遍历中找到最大子数组的和。
通俗解释
假设你有一个数组比如 [-2, 1, -3, 4, -1, 2, 1, -5, 4]你想找出这个数组中和最大的子数组。Kadane’s Algorithm通过以下步骤来完成这个任务
从左到右遍历数组你会逐个看数组中的每个数字。累积当前的和对于每个数字你有两种选择 要么继续把它加到之前的子数组和里扩展现有的子数组。要么丢弃之前的子数组从这个数字重新开始一个新的子数组。 更新最大和每当你计算出一个新的子数组和时记录下目前为止遇到的最大值。
具体的步骤如下 假设一开始你的数组是 [-2, 1, -3, 4, -1, 2, 1, -5, 4]我们先从第一个数字开始。 第一个数字是 -2这就是目前为止最大的子数组和所以暂时记录为最大值。 接着看下一个数字 1。你现在有两个选择 继续加-2 1 -1即把1加到前面的子数组[-2]上。重新开始直接从1开始子数组就变成了[1]。 很显然1比-1大所以你选择从1重新开始一个子数组并更新最大和为1。 再看下一个数字 -3你又有两个选择 继续加1 (-3) -2。重新开始从-3开始子数组变成[-3]。 你会选择继续加但最大和仍然保持不变为1。 继续这个过程直到遍历完整个数组每次你都比较是继续累加还是重新开始子数组并始终记录出现过的最大子数组和。
最终在这个例子里你会发现最大子数组是 [4, -1, 2, 1]它的和是 6。
核心思想总结
Kadane’s Algorithm用一种局部最优解逐步构建出全局最优解。通过在每个位置上选择是继续累加还是重新开始子数组你能够高效地找到整个数组的最大子数组和。每次你只关心当前元素以及前面累加的结果这使得算法可以在**O(n)**的时间内完成问题的求解。
class Solution {
public:int maxSubArray(vectorint nums) {//首先利用第1个元素分别初始化局部最优解和全局最优解int current_sum nums[0];int max_sum nums[0];for(int i 1; i nums.size(); i) {//首先更新当前局部最优解, 对当前元素无非2种选择:1.作为新的子数组起点2.作为当前子数组的末尾//我们对比这两种情况的子数组和将最大值作为局部最优解。//这行代码很巧妙不仅更新了局部最优解也可以设置新的子数组起点current_sum max(nums[i], current_sum nums[i]);//更新完局部最优解之后紧接着和全局最优解进行对比更新全局最优解max_sum max(current_sum, max_sum);}return max_sum;}
};是的Kadane’s Algorithm**属于动态规划Dynamic ProgrammingDP**的一种具体实现。
这行代码很巧妙不仅更新了局部最优解也可以设置新的子数组起点
current_sum max(nums[i], current_sum nums[i]);这行代码确实是Kadane’s Algorithm中最巧妙的地方关键在于它同时做了两件事 更新局部最优解current_sum max(nums[i], current_sum nums[i]);的核心在于它选择了当前子数组的最优策略。它计算了两种可能的情况 nums[i]直接将当前元素作为新的子数组的起点丢弃之前的累积和。current_sum nums[i]将当前元素加到之前已经计算出来的子数组和中继续扩展当前子数组。 通过比较这两种情况算法能在每个元素上做出最优决策即决定当前子数组是否应该继续累积还是应该重新开始。 自动设定新子数组起点当nums[i] current_sum nums[i]时这意味着累加前面的子数组和反而让和变小了因此此时就选择从nums[i]重新开始一个新的子数组。也就是说当前元素本身就大于累积的和时它就自然成为新的子数组的起点。这样就无需显式地去标记子数组的起点算法通过比较自动决定何时重置。
例子解释
以数组 [-2, 1, -3, 4, -1, 2, 1, -5, 4] 为例我们逐步解释这行代码的行为
开始时current_sum -2max_sum -2遍历到 1 时current_sum max(1, -2 1) 1此时直接从1重新开始max_sum 更新为 1。遍历到 -3 时current_sum max(-3, 1 - 3) -2继续累加但max_sum保持不变。遍历到 4 时current_sum max(4, -2 4) 4重新开始一个新的子数组max_sum 更新为 4。
通过这种方式每次都能判断是扩展子数组还是从当前元素重新开始并确保每一步都在寻找最优解。
巧妙之处总结
简洁高效通过一个简单的 max 比较Kadane’s Algorithm不仅做到了局部最优解的更新还自动完成了子数组的起点设定。相比于需要显式地处理每个子数组的起点和终点的其他算法Kadane’s Algorithm更加简洁、优雅。避免冗余操作无需存储额外的信息如子数组的起点或终点减少了空间开销同时保持了O(n)的时间复杂度。
这就是为什么Kadane’s Algorithm被认为是一个非常经典且高效的解决最大子数组和问题的算法。
为什么Kadane’s Algorithm是动态规划 重叠子问题动态规划的核心思想之一是通过解决子问题来解决更大的问题。在Kadane’s Algorithm中每个子数组和的最大值都依赖于前一个子数组的解。也就是说当前位置的最优解依赖于前一个位置的最优解这是“重叠子问题”的特性。 例如在当前位置i我们只需要知道位置i-1处的最大子数组和就能决定是否要把当前元素nums[i]加入到前面的子数组中还是从当前元素重新开始。 最优子结构动态规划要求问题具有最优子结构即全局问题的最优解可以由子问题的最优解构造得到。在Kadane’s Algorithm中整个数组的最大子数组和可以通过一系列局部最大子数组和的比较来得到。 Kadane’s Algorithm在每个步骤中都保持着一个局部最优解即以当前元素为结尾的最大子数组和并通过比较这些局部最优解来找到最终的全局最优解。
Kadane’s Algorithm的动态规划状态转移方程
动态规划常常有一个状态转移方程用来更新每个子问题的最优解。Kadane’s Algorithm的状态转移方程可以表述为
current_sum max(nums[i], current_sum nums[i])
这意味着 对于当前的元素nums[i]我们有两个选择 把它加到前面的子数组上current_sum nums[i]。或者从当前元素开始一个新的子数组nums[i]。 这就是状态转移的过程通过选择这两个选项中的较大值来更新current_sum从而实现动态规划的“状态更新”。
动态规划特征总结
状态以当前位置结尾的最大子数组和即current_sum。状态转移方程current_sum max(nums[i], current_sum nums[i])。最优解通过遍历所有状态即每个元素为结尾的最大子数组和找出其中的最大值。
动态规划的优化
Kadane’s Algorithm只需要常数空间来记录当前的子数组和以及最大子数组和因此它是空间优化后的动态规划版本。相比于一般的动态规划需要维护一个额外的数组来保存所有子问题的解Kadane’s Algorithm只需维护两个变量current_sum和max_sum这使得它的空间复杂度为O(1)。
结论
Kadane’s Algorithm确实属于动态规划的一种只是它通过非常高效的方式解决了最大子数组和的问题避免了使用更多的空间来存储中间结果。
