【剑指Offer 31】连续子数组的最大和

题目：输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。

代码如下：

package demo;

/**
 * 连续子数组的最大和
 * 
 * 解法：分析数组的规律
 * 
 * @author xiangdonglee
 *
 */
public class Test31 {
    /**
     * @param arr
     *            输入的数组
     * @return 最大的连续子数组的和
     */
    public static int findGreatestSumOfSubArray(int[] arr) {
        // 入参校验
        if (arr == null || arr.length < 1) {
            throw new IllegalArgumentException("Array must contain an element!");
        }
        // 记录最大的子数组和，开始时设为最小的整数
        int max = Integer.MIN_VALUE;
        // 当前的和
        int curSum = 0;
        // 数组遍历
        for (int i : arr) {
            // 如果当前和小于等于0，就设置当前和为当前值
            if (curSum <= 0) {
                curSum = i;
            }
            // 如果当前和大于0，就累加当前和
            else {
                curSum += i;
            }
            // 更新记录到的最大的子数组和
            // 因为max初始值为最小的整数，因此该条件初始时一定成立，刚开始会更新max的值
            if (max < curSum) {
                max = curSum;
            }
        }
        return max;
    }

    public static void main(String[] args) {
        int[] data1 = { 1, -2, 3, 10, -4, 7, 2, -5 };
        System.out.println(findGreatestSumOfSubArray(data1));
        int[] data2 = { -2, -8, -1, -5, -9 };
        System.out.println(findGreatestSumOfSubArray(data2));
        int[] data3 = { 2, 8, 1, 5, 9 };
        System.out.println(findGreatestSumOfSubArray(data3));
    }
}

来源：http://blog.csdn.net/derrantcm/article/details/46736967