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

是一道有点绕到我的题目，记录一下方便回顾。

1. 动态规划思想，先把走到第i-1步的最好结果求出来，走到第i步的时候，根据第i步的结果决定①带着第i-1步的结果继续走；②放弃第i-1步的结果，这一步就当从头开始。
2. sum记录最后返回的最好的结果。dp1是走到arr这个值之前的连续多步的最大和，在arr这里，先判断一下dp1是否小于0，如果小于等于0可以直接扔了，把arr当作第一步。如果大于0就留着，dp1+arr作为目前连续多步的最大和。再和sum比较一下，决定留着哪一个。

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        //dp
        int sum=array[0];
        int dp1=0;
        int dp2=0;
        for(int arr:array){
            dp2=arr;
            dp2+=Math.max(dp1,0);
            sum=Math.max(sum,dp2);
            dp1=dp2;
        }
        return sum;
    }
}