题目：
输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。
求所有子数组的和的最大值。要求时间负责度为O(n)。
分析：从第一个位置开始累加求和，结果为负数时候放弃前面的累加和重新计算。
static int MaxSum(int arr[], int n) { int currentSum = arr[0]; int ans = currentSum; for (int i = 1; i < n; i++) { currentSum = Math.max(currentSum + arr[i], arr[i]); ans = Math.max(ans, currentSum); } return ans; }
原文：http://www.cnblogs.com/silianbo/p/4842651.html