算法:最大子数组和

这道题使用的是动态规划思想Kadane算法目标是在数组中找到一个连续子数组使这个子数组元素之和最大。算法从数组的第一个元素开始向后遍历并维护两个变量一个变量表示“以当前元素结尾的连续子数组的最大和”。另一个变量表示“遍历到目前为止出现过的最大连续子数组和”。对于数组中的每一个元素都要思考一个问题当前元素应该接到前面的连续子数组后面还是自己重新开始形成一个新的连续子数组具体来说如果前面累计得到的和再加上当前元素比当前元素本身还大那么说明前面的部分对结果有贡献应该继续保留把当前元素接在后面。如果前面累计得到的和再加上当前元素还不如当前元素本身大那么说明前面的部分已经成为负担应该舍弃之前的连续子数组从当前元素重新开始计算。因此每遍历到一个新元素时都计算继续延伸之前的连续子数组得到的和从当前元素重新开始得到的和取两者中的较大值作为“以当前元素结尾的最大连续子数组和”。随后再将这个结果与历史记录中的最大值进行比较如果当前得到的连续子数组和更大就更新全局最大值否则保持原来的最大值不变。整个过程只需要遍历数组一次。从本质上看这个算法利用了这样一个规律如果一个连续子数组的和已经变成负数那么它只会拖累后面的结果因此没有必要继留如果它是正数则可以帮助后面的元素获得更大的和因此应该保留。最终当遍历结束时记录下来的全局最大值就是整个数组中的最大连续子数组和。int maxSubArray(vectorint nums) { int pre0,maxAnsnums[0]; for(const auto x:nums) { premax(prex,x); maxAnsmax(maxAns,pre); } return maxAns; }