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

动规
dp[i]表示第i个位置的最大和
判断前一个位置的最大和dp[i-1]是正是负
正数：dp[i]=dp[i-1]+array[i]
负数dp[i]=array[i];
同时用一个变量max记录最大值

 public int FindGreatestSumOfSubArray(int[] array) {
        int dp[]=new int[array.length];
        dp[0]=array[0];
        int max=dp[0];
        for(int i=1;i<array.length;i++){
            if(dp[i-1]>=0){
                dp[i]=dp[i-1]+array[i];
                max=max>dp[i]?max:dp[i];
            }
            else{
                dp[i]=array[i];
                max=max>dp[i]?max:dp[i];
            }
        }
        return max;
    }