JZ30：连续子数组的最大和

解法1：不是看当前的值，而是看当前的累计值，

如果当前累计为负数，那么加上现在这个数，肯定和就小了，所以继续从当前开始累计，如果为正，那就继续加，但是要时刻保存下最大值来，因为后面的累计有可能小。

public int FindGreatestSumOfSubArray(int[] array) {
        if(array.length==0){
            return 0;
        }
        int total=array[0];//当前的前面的和累计
        int maxsum=array[0];//记录可能的最大值
        for(int i=1;i<array.length;i++){
            if(total>=0){
                total+=array[i];
            }
            else{
                total=array[i];
            }
            if(maxsum<total){
                maxsum=total;
            }
        }
        return maxsum;
    }

解法2：使用动态规划法，定义一个dp数组记录从第一个数字开始到当前数字的最大累加和。

每当前一个累加和大于0时，进行dp[i]的更新。
最后遍历dp数组，取最大的dp[i]返回。

    public int maxsumofSubarray (int[] arr) {
        // write code here
        int len = arr.length;
        int res = Integer.MIN_VALUE;
        //用tmp数组记录从0出发到当前数字能累加的最大数
        int[] dp = new int[len];
        //先初始化它
        for(int i=0; i < len; i++){
            dp[i] = arr[i];
        }
        //开始遍历
        for(int i=1; i < len; i++){
            //当前面已累加和大于0时，加上肯定比当前的数字大
            dp[i] = (dp[i-1] > 0 ? (dp[i-1]+ arr[i]) : dp[i]);
        }
        //进行比较，选择出最大的累加和
        for(int i=0; i < len; i++){
            res = Math.max(res, dp[i]);
        }
        return res;
    }