Leetcode 53 最大子数组和

题意理解：

? ? ? ? 给定一个数列，求连续的子序列的和最大可以是多少？

????????子数组?是数组中的一个连续部分。

? ? ? ? 比如：

????????nums = [-2,1,-3,4,-1,2,1,-5,4]

? ? ? ? 最大子序列的和：6（4-1+2+1）

解题思路：

? ? ? ? 使用贪心的思路来解题，则需要定义局部最优解和全局最优解，及分析之间的关系。

? ? ? ? 当遍历到第i个元素时，当前子序列和为负数时，与其继续累加子序列的值不如设其之前的子序列。

? ? ? ? 因为：负数之后拖累子序列和，

? ? ? ? 所以，我们需要再合适的地方舍弃子序列和为负的子序列——即合适的位置开启一个结果可能为正的子序列。

? ? ? ? 又因为我们要求一个最大的子序列和

? ? ? ? 所以我们需要一个值来记录最大子序列和，其总揭露最大子序列和和当前子序列和的最大值。

? ? ? ? 最终，我们能得到连续子序列的最大值。

1.贪心解题

我们使用result来记录最大子序列和，curSum来记录当前子序列和。

注意：

????????当且仅当数组只有一个元素时，则最大子序列和即为这个元素，即使这个元素可能时负数。

? ? ? ? 如果一个序列的元素全为负数的话，其最大子序列和为该序列中最大的负数，因为其和任何一个负数相加都会变得更小。

所以result和curSum从nums[0]初始化，遍历应从i=1处开始。

? ? ? ? 当只有一个元素时，返回当前值，

????????curSum为负，子序列和总是从0累加当前值。

public int maxSubArray(int[] nums) {
        int result=nums[0];
        int curSum=nums[0];
        for(int i=1;i<nums.length;i++){
            curSum=Math.max(curSum,0);//不从负数累加
            curSum+=nums[i];
            result=Math.max(curSum,result);
        }
        return result;
    }

2.分析

时间复杂度：O(n)

空间复杂度：O(n)