题目：输入一个整型数组，数组里有正数也有负数。数组中一个或者连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)
分析：首先需要考虑的条件：数组里有正数也有负数，根据这个条件，从数组第一个元素开始，temp累计相加，当temp增加时，我们就将temp赋值给sum。当temp为小于0 ，我们就将temp归为0，但是此时sum还是保存之前的最大值。temp接下来继续这样累加。。
#include "stdafx.h" #include <iostream> using namespace std; int FindMaxSum(int pData[],int length) { if (pData == NULL || length <= 0) return 0; int sum = 0; int temp = 0; for (int i = 0; i < length; ++i) { temp += pData[i]; if (temp>sum) sum = temp; if (temp <= 0) temp = 0; } return sum; } int _tmain(int argc, _TCHAR* argv[]) { int data[] = { 1,-7,4,3,-2,5 }; cout << FindMaxSum(data, 6) << endl; return 0; }
这题还可以用动态规划去做。
判断最后一个数字之外的和是大于0 还是小于0.动态规划总是从最后一个开始入手。
原文：http://www.cnblogs.com/menghuizuotian/p/3812746.html