五百年前

这个问题可以有很多求解方案，但是我认为下面是一个最优的方案，来源于《数据结构与分析》。下面的求解方案很巧妙，时间复杂度是O(n).可以多参考其中的思想。

package com.sea.leetcode;

/**
 * Created by Sea on 2016/11/25.
 * 一个整形数组，包含有整数，负数。求最大连续子数组的和。
 */
public class MaxSubSum {
    public static int maxSubSum(int[] arr) {
        int arrLength = arr.length;
        int maxSum = 0, thisSum = 0;
        for (int i = 0; i < arrLength; i++) {
            thisSum += arr[i];
            if (thisSum > maxSum) {
                maxSum = thisSum;
            } else if (thisSum < 0) {
                thisSum = 0;
            }
            
        }
        return maxSum;
    }

    public static void main(String[] args) {
        System.out.println(maxSubSum(new int[]{1,-1,2,-1,3,-1}));
    }
}