leetcode53—最大子数组和（kadane算法）

目录

题目介绍

解决思路

代码实现

证明

---

题目介绍

     kadane算法是一种用于解决最大子数组和问题的动态规划算法。

     现有一个整数数组nums，找出一个最大和的连续子数组（子数组是数组中的一个连续部分，可以为一个数），并返回其最大和。

     示例：nums = [ -2,1,-3,4,-1,2,1 ]，输出：6（子数组[4,-1,2,1] 的和最大）。

     范围：1 <= nums.length <= 1e5， -1e4 <= nums <= 1e4

     题目链接：最大子数组和

解决思路

     暴力的解法就是一个一个遍历找最大值，这虽简单但时间复杂度是O(N^2)把最大范围代入可以看到是O(1e10)很显然会超时。

     我们换个思路倒着看。比如以下标1为结尾（上面的示例），它会有[-2,1]或者[1]很显然最大是1。以下标3它有会有下面的几种情况：

其它依次类推，大家可能会想这时间复杂度不是没变吗？确实没变化但是可以对它进行优化把O(N^2)降为O(N)。其实某位置最大子数组和就只有两种情况：一它本身。二它与前面最大子数组的结合（证明请看文章最后），只需要判断这两个大小即可。这就是kadane算法的思想。

代码实现

     题目中给出的范围最大的情况是1e9如果用int类型可能会溢出，要换成long long类型。

     定义current_max和global_max这是用于确定当前最大值和全局最大值，然后将数组第一位赋值给它们，因为数组第一位最大就是自己。接下来遍历数组找最大和即可。

int maxSubArray(vector<int>& nums) 
{long long current_max = nums[0], global_max = nums[0];for(int i = 1; i < nums.size(); i++){current_max = max((long long)nums[i], current_max + nums[i]);global_max = max(current_max, global_max);}return global_max;
}

     注意：第六行要把nums[i]强转成long long类型，因为max函数只支持同种类型的比较。

证明

     假设现在有个数组，现正在对它的第n位找最大值，该位值为X。并且已知它的上一位最大和为M。根据kadane算法在n位最大和就只有[M，X]或[X]。

     我们用反证法，假设[M，X]和[X]都不是最大子数组，令[T，X]是最大子数组，T的长度可以大于M的长度也可以小于M的长度但不能为0。

     证明该式子[T，X] > [M，X]，如果能证出那[M，X]和[X]都不是最大和反之则是。先把[T，X]改为sum(T) + X，同理再把[M，X]改为sum(M) + X。把X抵消掉则sum(T) > sum(M)，显然根据上面的已知条件这是相互矛盾的。故最大和就只能是[M，X]或[X]。