Leetcode 最大子数组和

使用“Kadane’s Algorithm”来解决。

Kadane’s Algorithm 在每个步骤中都保持着一个局部最优解，即以当前元素为结尾的最大子数组和(也就是局部最优解)，并通过比较这些局部最优解和当前的全局最优解来找到最终的全局最优解。

Kadane’s Algorithm的核心思想是：在遍历数组的过程中，动态地计算出以每个元素结尾的最大子数组和，并用一个变量来记录出现过的最大值。简单来说，它帮我们找到了一种巧妙的方式，在一次遍历中找到最大子数组的和。

通俗解释：

假设你有一个数组，比如 [-2, 1, -3, 4, -1, 2, 1, -5, 4]，你想找出这个数组中和最大的子数组。Kadane’s Algorithm通过以下步骤来完成这个任务：

1. 从左到右遍历数组：你会逐个看数组中的每个数字。
2. 累积当前的和：对于每个数字，你有两种选择：
   • 要么继续把它加到之前的子数组和里，扩展现有的子数组。
   • 要么丢弃之前的子数组，从这个数字重新开始一个新的子数组。
3. 更新最大和：每当你计算出一个新的子数组和时，记录下目前为止遇到的最大值。

具体的步骤如下：

• 假设一开始你的数组是 [-2, 1, -3, 4, -1, 2, 1, -5, 4]，我们先从第一个数字开始。

• 第一个数字是 -2，这就是目前为止最大的子数组和，所以暂时记录为最大值。

• 接着看下一个数字 1。你现在有两个选择：

  1. 继续加：-2 + 1 = -1，即把1加到前面的子数组（[-2]）上。
  2. 重新开始：直接从1开始，子数组就变成了[1]。

  很显然，1比-1大，所以你选择从1重新开始一个子数组，并更新最大和为1。

• 再看下一个数字 -3，你又有两个选择：

  1. 继续加：1 + (-3) = -2。
  2. 重新开始：从-3开始，子数组变成[-3]。

  你会选择继续加，但最大和仍然保持不变为1。

• 继续这个过程，直到遍历完整个数组，每次你都比较是继续累加还是重新开始子数组，并始终记录出现过的最大子数组和。

最终，在这个例子里，你会发现最大子数组是 [4, -1, 2, 1]，它的和是 6。

核心思想总结：

• Kadane’s Algorithm用一种局部最优解逐步构建出全局最优解。通过在每个位置上选择是继续累加还是重新开始子数组，你能够高效地找到整个数组的最大子数组和。
• 每次你只关心当前元素，以及前面累加的结果，这使得算法可以在**O(n)**的时间内完成问题的求解。

class Solution {
public:
    int maxSubArray(vector<int>& 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 Programming，DP）**的一种具体实现。

这行代码很巧妙，不仅更新了局部最优解，也可以设置新的子数组起点

current_sum = max(nums[i], current_sum + nums[i]);

这行代码确实是Kadane’s Algorithm中最巧妙的地方，关键在于它同时做了两件事：

1. 更新局部最优解：current_sum = max(nums[i], current_sum + nums[i]);的核心在于它选择了当前子数组的最优策略。它计算了两种可能的情况：

   • nums[i]：直接将当前元素作为新的子数组的起点，丢弃之前的累积和。
   • current_sum + nums[i]：将当前元素加到之前已经计算出来的子数组和中，继续扩展当前子数组。

   通过比较这两种情况，算法能在每个元素上做出最优决策，即决定当前子数组是否应该继续累积，还是应该重新开始。

2. 自动设定新子数组起点：当nums[i] > current_sum + nums[i]时，这意味着累加前面的子数组和反而让和变小了，因此此时就选择从nums[i]重新开始一个新的子数组。也就是说，当前元素本身就大于累积的和时，它就自然成为新的子数组的起点。这样就无需显式地去标记子数组的起点，算法通过比较自动决定何时重置。

例子解释：

以数组 [-2, 1, -3, 4, -1, 2, 1, -5, 4] 为例，我们逐步解释这行代码的行为：

• 开始时：current_sum = -2，max_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是动态规划？

1. 重叠子问题：动态规划的核心思想之一是通过解决子问题来解决更大的问题。在Kadane’s Algorithm中，每个子数组和的最大值都依赖于前一个子数组的解。也就是说，当前位置的最优解依赖于前一个位置的最优解，这是“重叠子问题”的特性。

   • 例如，在当前位置i，我们只需要知道位置i-1处的最大子数组和，就能决定是否要把当前元素nums[i]加入到前面的子数组中，还是从当前元素重新开始。

2. 最优子结构：动态规划要求问题具有最优子结构，即全局问题的最优解可以由子问题的最优解构造得到。在Kadane’s Algorithm中，整个数组的最大子数组和可以通过一系列局部最大子数组和的比较来得到。

   • Kadane’s Algorithm在每个步骤中都保持着一个局部最优解，即以当前元素为结尾的最大子数组和，并通过比较这些局部最优解来找到最终的全局最优解。

Kadane’s Algorithm的动态规划状态转移方程

动态规划常常有一个状态转移方程，用来更新每个子问题的最优解。Kadane’s Algorithm的状态转移方程可以表述为：

• current_sum = max(nums[i], current_sum + nums[i])

这意味着：

• 对于当前的元素nums[i]，我们有两个选择：

  1. 把它加到前面的子数组上（current_sum + nums[i]）。
  2. 或者，从当前元素开始一个新的子数组（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确实属于动态规划的一种，只是它通过非常高效的方式解决了最大子数组和的问题，避免了使用更多的空间来存储中间结果。