JZ30 连续子数组的最大和

1. 递归 dp 代表 以i结尾的 连续数组的最大值 注意区别 题目问的是当前数组的 连续数组的最大值
   dp代表 以这个点结尾的 连续数组的最大值
   然后通过比较 每个点的 dp 选出当前数组的最大

相当于获得了 每个点 以这个点结尾向前的连续数组的最大值 dp[i]
dp和前一个点有关 如果前一个点的dp>0 那么必然dp = dp + nums[i] 因为需要当前点结尾
如果 dp < 0 那么说明之前的都没有用 那么只需要 dp = num[i] 就行了

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int dp = 0;
        int res = array[0];

        for(int i =0; i<array.length; i++){
            //dp = Math.max(dp+array[i],array[i]);
            if(dp > 0) dp = dp+array[i];
            else {dp = array[i];}

            res = Math.max(res,dp);
        }
        return res;
    }
}

2.

思想就是如果 该数之前的和 加这个数小于零， 那么之前的都不能加入到最大和的数组中。
但是这样会导致后面为负值 知道大于0 就还会继续加 因此需要Math.max(res,temp);
例如 【100，-1，-2，-3，-4】 这样temp最后会等于90 因此 还需要保存之前的最大值
同时 如果全部小于0 最后的值为0 因此需要判断 if(max_num < 0) return max_num
不如动态规划直接

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int temp = 0;
        int max_num = Integer.MIN_VALUE;
        int res = 0;

        for(int i =0;i<array.length; i++){
            if(temp + array[i] < 0) temp = 0;
            else{temp = temp + array[i];}
            res = Math.max(res,temp);
            max_num = Math.max(max_num,array[i]);
        }

        if(max_num < 0) return max_num;
        else return res;

    }
}