这是一个从另一个园友的博客上看到的题目，顺便求解分析一下~~
题目：
输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如，输入的数组为{1, -2, 3, 10, -4, 7, 2, -5}，和最大的子数组为3, 10, -4, 7, 2，
因此输出为该子数组的和18。
解法一：
1、分析：最简单直接的方法就是求出所有子数组的和，然后挑选出最大的值。
2、代码：
int FindMaxSubarraySum(int array[], int len)
{
int sum = 0, max = 0, i = 0, j = 0;
max = array[0];
for (i = 0; i < len; i++) {
sum = 0;
for (j = i; j < len; j++) {
sum += array[j];
if (max < sum) {
max = sum;
}
}
}
return max;
}
可以看到这是一个两重循环，它的时间复杂度为O(n(n + 1)/2)，很显然大于O(n)，不符合题目要求。
解法二：
1、分析：
既然题目要求时间复杂度为O(n)，那么一定存在这样的解（因为这是一个考试题嘛），如果要达到O(n)，那么一定是所有数组元素从左往右只遍历一次。
既然是求和那么就需要将子数组的元素依次累加，问题来了，哪里是最大和子数组的起始点和结束点？结束点很好判断，与之前的最大值进行对比，如果比之前的大，那么当前的元素就是当前已知的最大和子数组的终点。但是起始点呢？貌似一下子看不到。
模拟一下过程，假设数组为a0,a1,...,an，max为当前已知的子数组最大和，sum(i, j)为子数组（ai, ..., aj）的和。为了下面分析的严谨性，假定数组元素有正有负，它的最大和子数组的元素个数不小于3个。
如果(ak,..., af)为最大和子数组，最直观地可以看到，一定有ak > 0, af > 0，仔细分析一下还可以得出有sum(k, k + 1) > 0, sum(k, k + 2) > 0, ..., sum(k, f-1) > 0。所以起始点是一个正数，即ak > 0, 也就是sum(k, k) > 0的地方。
综上，所以我们只需要从左往右遍历，累加数组元素值到sum，判断其与max的值，如果大于max则更新max的值为sum，如果小于零，则将sum置为0，如果大于零则继续累加下一个元素，这样不断寻找最大的和直到数组结束。
2、代码：
int FindMaxSubarraySum(int array[], int len)
{
int sum = 0, max = 0, i = 0;
max = array[0];
for (i = 0; i < len; i++) {
sum += array[i];
if (max < sum) {
max = sum;
}
if (sum < 0) {
sum = 0;
}
}
return max;
}
可以看出只用一重循环就可以求出结果，时间复杂度为O(n)。不仅适应数组元素有正有负的情况，也适应数组全为负数或全为正数的情况。
原文：http://www.cnblogs.com/Monarudo/p/3586669.html