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

• 如果a+b<b，sum变小，舍弃a,下一轮从b+c开始，如果b>sum，sum=b
• 如果a+b>b，sum变大，下一轮从a+b+c开始，如果a+b>sum,sum=a+b

• 动态规划是指不重复计算，将计算过的值存下来

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
//         return nornal(array);
//         return dp(array);
        return optDp(array);
    }
//     超时
    public int normal(int[] array){
        int max = array[0];
        for(int i=0;i<array.length;i++){
            int sum = 0;
            for(int j=i;j<array.length;j++){
                sum+=array[j];
                if(max<sum)max=sum;
            }
        }
        return max;
    }
    
//     dp存放下标截止的最大和
    public int dp(int[] array){
        int[] dp = new int[array.length];
        int max = array[0];
        dp[0] = array[0];
        for(int i=1;i<array.length;i++){
            dp[i] = dp[i-1]+array[i];
            if(dp[i]<array[i])dp[i]=array[i];
            if(max<dp[i])max=dp[i];
        }
        return max;
    }
//     优化方案
    public int optDp(int[] array){
        int max = array[0];
        int sum=0;
        for(int i=0;i<array.length;i++){
            sum = Math.max(sum+array[i],array[i]);
            max = Math.max(sum,max);
        }
        return max;
    }
}