53 最大子序和

01

题目信息

题目地址：https://leetcode-cn.com/problems/maximum-subarray/

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶:如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

02

解法一：动态规划

首先我们去划分一下子问题。整个数列的最大子序和，他是可能就等于n-1的最大子序和，它也可以是个新的值。至少是这两种情况

情况一：

[-1,3,1,-4,1]
当前数列的最大子序和就是4也就是(1,2)项。
它也是前n-1项的最大子序和

情况二：

[-1,3,1,-4,5]
当前数列的最大子序和是5也就是(4)项
而前n-1项的数列最大子序和还是4也就是(1,2)项

每次往后迭代一个值它的结果可能变化也可能不变化，这就是记录的点。我们算出当前最大的值然后与之前的result进行比较可能更新result也可能不变，进行下个迭代再次算当前最好的值再与result比较。

那么唯一的问题就是当前的最大值是怎么计算的，就是我们不是去暴力全部序列，而是跳过不必要的，即当前面sum为负的时候，即使后面有大的也没必要加上负的，也就是直接跳序列的首指针来达到减少遍历吃次数

[2,-1,-3,-4,7]
我们大概需要四个变量
result = 0 // 结果
i = 0 // 序列的首指针
j = 0 // 序列的尾指针
sum = 0 //当前序列和

但我们记录sum就代表i至j了，所以不用指针变量 代码如下：

public int maxSubArray(int[] nums) {
    //sum表示上一个最大子序和也就是dp[n-1]
    int sum = 0;
    int result = nums[0];
    for(int i = 0; i < nums.length; i++){
        sum = sum > 0 ? sum + nums[i] : nums[i];
        max = max > sum ? max : sum;
    }
    return max;
}

03

总结

这题的话虽然是简单但还是要点思考的，用到了动态与贪心的思想合起来减少了遍历一遍的次数。关于自顶向下的分治比较适合之后筹备的另一个系列做例子这里不展开。