题解 | #连续子数组的最大和#TOP72

思路:
1.两种方法，dp动态
2.贪心

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        //dp[i] 以 i 结尾的数组最大和
        if(array == null){
            return 0;
        }
        if(array.length == 1){
            return array[0];
        }
//         int[] dp = new int[array.length];
//         dp[0] = array[0];
//         int result = array[0];
        
//         for(int i = 1;i < array.length ; i++){
//             dp[i] =  Math.max(dp[i-1] +array[i], array[i]);
//             result = Math.max(dp[i],result);
//         }
//         return result;
        int result = 0;
        int temp = 0;
        int max = Integer.MIN_VALUE;
        for(int i = 0;i<array.length;i++){
            result += array[i];
            if(max < result){
                max = result;
            }
            if(result < 0){
                //题目是连续子数组
                //如果不重置，后面累加如果数字为负数，将更小,如果为正数也是变小
                result = 0;
            }
        }
        return max;

    }
}