每天一算法（求子数组的最大和）
题目：
输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。
例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，
因此输出为该子数组的和18。
解题思路：
因为时间复杂度是0(n),所以我们只能用一次遍历就要求出最大的子数组和，所以我的想法是这样：以空间换取时间。
用一个和原来数组一样大的临时数组记录遍历过程中的和，遍历过程中依次对每个Item都同样进行以下的动作：当遇到负数的时候，就把当前的Sum值记录到临时数组中，然后判断当前的Item的绝对值是否大于Sum,如果大于，将Sum恢复为原来的初始值，也就是Sum = 0,如果Item的绝对值小于Sum的话就把Sum += Item值。当然如果遍历过程中遇到的Item > 0的情况，直接Sum += Item.等到遍历结束后，从临时数组中捉取最大值就是最大的子数组和的值。
VS2010中运行程序如下：例子程序是正确的，，如果有什么错误，希望各位高手指定，，呵呵。。
#include<stdlib.h>#include<string>#include<iostream>using namespace std;int MaxArray(int *a,int n){if(0 == n)return 0;if(1 == n)return a[1];int *Index = new int[n];int max= 0;//最大值int Timmax = 0;//临时空间中，每个元素的值。for(int i = 0;i<n;i++){if(0 <= a[i]){Timmax += a[i];Index[i] = Timmax;}else{if(Timmax < -a[i]){Timmax = 0;Index[i] = 0;}else{Timmax += a[i];Index[i] = Timmax;}}if(max<Index[i])max = Index[i];}return max;}int main() { int anAry[] = {1, -2, 3, 10, -4, -3,7, 2, -5}; //int nMaxValue = MaxSubArraySum(anAry, sizeof(anAry)/sizeof(int)); int nMaxValue = MaxArray(anAry, sizeof(anAry)/sizeof(int)); cout << "最大的子数组和为：" << nMaxValue << endl; return 0; } 在网上搜的时候，，找到一个好象更简单的方法 ，，方法如下，，以供学习：
只要一次遍历就可以求出最大的子数组和，而且是很简单的就解决了，具体想法是这样，不断的累加每个数组元素，并用一个变量保存当前的最大值，累加的过程一直和该变量进行比对，如果大于最大值，就把当前的最大值保存下来，反复如此就可以求出最大值.
int MaxSum(int* a, int n){int nSum = 0;int nValue=0;for(int i = 0; i < n; i++){if (nValue <= 0) nValue = a[i];else nValue += a[i];if(nSum < nValue) nSum = nValue;}return nSum;}int _tmain(int argc, _TCHAR* argv[]){int anAry[] = {-2, 10,12, -20, 33};//int nMaxValue = MaxSubArraySum(anAry, sizeof(anAry)/sizeof(int));int nMaxValue = MaxSum(anAry, sizeof(anAry)/sizeof(int));cout << "最大的子数组和为：" << nMaxValue << endl;return 0;}