连续子数组的最大和 (贪心，动态规划) AcWing（JAVA）

输入一个 非空 整型数组，数组里的数可能为正，也可能为负。

数组中一个或连续的多个整数组成一个子数组。

求所有子数组的和的最大值。

要求时间复杂度为 O(n)。

数据范围：

数组长度 [1,1000]。
数组内元素取值范围 [−200,200][−200,200]。

样例：

输入：

[ 1，-2，3，10，-4，7，2，-5]

输出：

18 

解题思路： 本题是求子数组的最大值。

对于数组 [1，......，x，......... ，2]。用 变量s 记录 x 前一个子数组的值，若 s < 0 , x + s, 反而比 x 本身小，那么不如从 x 开始重新设立一个新的子数组。对于 s > 0 , s + x 一定要比 x 大，所以不如将 x 纳入 子数组 s 内 （不必担心 x 小于0，使新子数组值变小，因为res变量时刻在更新最大值）。对于 s = 0 的情况完全可以归纳到 s < 0 内。

理论成立代码如下：

class Solution {public int maxSubArray(int[] nums) {int res = -201;int s = 0;for(int x : nums){if(s < 0)s = 0;s = s + x;res = Math.max(res,s);}return res;}
}