*巧妙动态规划
1.每次推加当前值并判断到此积累是否有效
2.无效则进入下一个
3.有效则再判断是否波峰,是的话就尝试更新max
4.返回max
注意:题目说有正有负,测试用例有全负数的情况,所以记载一下最大负数,max为0的时候返回这个负数
*

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
      //开一个cur_val记录当前有效值,一个max记录当前最高峰值
        int cur_val=0;int max=0;
        //此处后来补充 题目说有正数有负数 运行用例怎么会有全负数的情况? 既然如此记录一下最大负数
        int max_f=-9999;
        //遍历数组
        for (int i=0;i<array.length;i++) {
            //补一手最大负数记录
            if(array[i]<0){
                if(array[i]>max_f){
                    max_f=array[i];
                }
            }
            cur_val+=array[i];
            //如果当前累计值小于等于0,表示之前走过的段无效,则更新 有效值 为0,且结束此次
            if(cur_val<=0){
                cur_val=0;
                continue;
            }
            //如果当前为峰顶,则尝试更新入max
            if(array[i]>0&&array[i+1]<=0){
                if(cur_val>max){
                    max=cur_val;
                }
            }
            //如果当前为结束,尝试把最后的有效值推入max
            if(i==array.length-1) {
                if (cur_val > max) {
                    max = cur_val;
                }
            }
        }
        //尝试返回max
        if(max==0){
            return max_f;
        }
        return max;
    }
}