编程之美 - 最大子数组和

问题导读：

1. 连续的子数组

2. 求和，并不需要返回位置

3. 输入值为正负整数 和 0

解决方案：

public class MaxSubArraySum {
    public static void main(String []args) {
        /*
         * 测试数组
         */
        int []arr1 = {1, 1, 1, 1, 1, 1};
        int []arr2 = {0, 0, 0, 0, 0, 0};
        int []arr3 = {-9, -2, -3, -5, -3};
        int []arr4 = {1, -2, 3, 5, -3, 2};
        int []arr5 = {0, -2, 3, 5, -1, 2};
        
        /*
         * 测试结果
         */
        System.out.println(
                "+：\t" + maxSum(arr1) + "\n" +
                "0：\t" + maxSum(arr2) + "\n" +
                "-：\t" + maxSum(arr3) + "\n" +
                "+-：\t" + maxSum(arr4) + "\n" +
                "+0-：\t" + maxSum(arr5)  
                );
        
    }
    
    static int maxSum(int []arr) {
        int nStart = arr[0];
        int nAll = arr[0];
        
        /*
         * 动态规划：
         * max{arr[i],arr[i]+start[i+1],all[i]}
         * 注：
         * arr[i] -> 第 i 个数值
         * arr[i] + start[i+1] -> 第 i 个 数值 加上 下一个数值
         * all[i] -> 当前最大子数组和
         */
        for(int i = 1; i < arr.length; i++) {
            nStart = Math.max(arr[i], arr[i]+nStart);
            nAll = Math.max(nStart, nAll);
        }
        return nAll;
    }
}