描述

难度：简单

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

示例 1：

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

示例 2：

输入：nums = [1]
输出：1

提示：

1 <= nums.length <= 3 * 104 -105 <= nums[i] <= 105

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/maximum-subarray 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这一题更准确的说，应该是一个贪心的题目。

但是在这里，我们用一维dp的方法来实现。

首先要明白的是：怎么样才能拿到最大的值？

比如：

[-2, 1, -3, 4, -1, 2, 1, -5, 4]

遍历这个数组

第一次  i=0，nums[i]=-2 , 当前位置的值： -2
第二次  i=1，nums[i]= 1 , 当前位置的值：-2 + 1 = -1  

问题就是第二次，加上当前的值 -1 ，既然是负数（比如我当前的值还小呢！），那还不如我直接出 i=1 的位置重新计算，加上
负数只会越来越小。
所以这个逻辑就出来了：
如果加上当前位置的值比我当前值小（也就是前面是负数），就直接从当前位置开始。

整合一下思路：

我们用一个变量记录截止到当前位置最大值、

 int max_ending_here = nums[0];
 int max_so_far = nums[0];

如果加上当前位置的值比我当前值小（也就是前面是负数），就直接从当前位置开始，那么：

        for (int i = 1; i < nums.length; i++) {
            max_ending_here = Math.max(nums[i], max_ending_here + nums[i]);
            max_so_far = Math.max(max_so_far, max_ending_here);
        }

这有点类似「滚动数组」的思想。

复杂度

时间复杂度：O(n)，其中 nn 为 \textit{nums}nums 数组的长度。我们只需要遍历一遍数组即可求得答案。 空间复杂度：O(1)。我们只需要常数空间存放若干变量。

题解

public class 最大子序和53 {
    public static void main(String[] args) {
        int[] nums = new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4,99};
        System.out.println(maxSubArray(nums));
    }

    /**
     * 动态规划
     *
     * 规律就是：前面的数加起来，只要大于0，肯定是要的
     *
     * @param nums
     * @return
     */
    static int maxSubArray(int[] nums) {
        int max_ending_here = nums[0];
        int max_so_far = nums[0];
        for (int i = 1; i < nums.length; i++) {
//            不管前面多长，反正我告诉你截止到你位置最大的值
//            -2, 1, -3, 4, -1, 2, 1, -5, 4
//            -2, 1,  1, 4, 3,  5, 6, 1,  5
            max_ending_here = Math.max(nums[i], max_ending_here + nums[i]);
            max_so_far = Math.max(max_so_far, max_ending_here);
        }
        return max_so_far;
    }
     /**
     * 和上面的都是一样的，理解可能会好一点
     *
     * @param nums
     * @return
     */
    static int maxSubArray2(int nums[]) {
        int ans = nums[0];
        int sum = 0;
        for (int num : nums) {
            if(sum > 0) { 
            // if (sum + num > num) {  //可以写成这样，这样写就和上面的一样思想了
                sum = sum + num;
            } else {
                sum = num;
            }
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}