Java动态规划例题——最大子序和

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

示例 1：

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

输入：nums = [1]
输出：1
示例 3：

输入：nums = [0]
输出：0
示例 4：

输入：nums = [-1]
输出：-1
示例 5：

输入：nums = [-100000]
输出：-100000

提示：

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

答案：

public static int maxSubArray(int[] nums) {
        int sum = 0, max = 0,M = nums[0];
        
        for (int i = 0; i< nums.length; i++){
            sum += nums[i];
            if (Max < nums[i] ){
                Max = nums[i];
            }
            if (max < sum){
                max = sum;
            }
            if (sum < 0){
                sum = 0;
            }
        }
        if (Max < 0)
            max = Max;
        return max;
    }

分析：
1.找单个最大的值

int Max = nums[0];
for(int i=0;i<nums.lenght;i++){
	if(Max<nums[i]){
		Max = nums[i];
	}
}

2.如果所遍历的序列长为n，前i个值均为负数，则直接从i+1个值开始遍历；
原因：1.如果所求的序列，其前i个值均为负数，那么无论其后值如何，i+1 到 n 的和一定会比 i 到 n的和大
证：已知 i 为负数，则 [i+（i+1）+。。。+n] - [(i+1) + (i+2)+ … +n] = i < 0;
即 [i+（i+1）+…+n] < [(i+1) + (i+2)+ … +n]

因此：

 int sum = 0, max = 0；
//初始化，sum = 0，因为0加任何数都等于该数本身，不会对数值照成影响
        for (int i = 0; i< nums.length; i++){
            sum += nums[i];
            if (max<sum){ 
                max = sum;
            }
            if(sum < 0 ){
            	sum = 0;  //当判断到前k 到 k+j个数相加为负值，则可把[k+(k+1)+...+(k+j)]理解成一个整体，
            			//看作为 i ,即[k+(k+1)+...+(k+j)] = i,则按照上面的推理，可直接跳过其的遍历求和。
            			//初始化 sum = 0 ，开始下一位置i++的遍历求和
            }
        }

3.如果序列的值全为负数，按上面的推理，则最大的序列和为该序列最大的某一个单值，在1中，我们已经求到了序列最大单值Max，直接赋值给max

if (Max < 0)//如果最大值都小于0，那就间接说明该序列的值全为负数
     max = Max;