这周我们没有了四则运算，又出现的新的任务：返回一个整数数组中最大子数组的和
刚一看感觉还是不难的，只需将所有子数组的和都”+“起来再比较就能算出最大值，但是这是比较笨的方法。
后来有个同学提出使用动态规划的方法可以实现，听他讲了思路之后，我觉得这个比第一个笨方法要好 ：）
然而后来我找到一个比较简便的方法：
要是累加过程中和小于0，那么和最大的子数组不会包含前面子数组，之后将和归0，从下个元素重新开始计算。
代码：
1 #include<iostream> 2 using namespace std; 3 4 int main() 5 { 6 int i,num; 7 cout << "请输入数组元素个数： " ; 8 cin >> num; 9 int *arr = new int[num]; 10 cout << "请依次输入数组元素" << endl; 11 for (i = 0; i < num; i++) 12 { 13 cin >> arr[i]; 14 } 15 int MaxSum = 0; 16 int CurSum = 0; 17 for (i = 0; i<num; i++) 18 { 19 CurSum += arr[i]; 20 if (CurSum > MaxSum) 21 { 22 MaxSum = CurSum; 23 } 24 if (CurSum < 0) 25 { 26 CurSum = 0; 27 } 28 } 29 cout <<"该数组中最大子数组的和是： "<< CurSum<<endl; 30 system("pause"); 31 32 return 0; 33 }
结果截图：
代码编写的过程中没有出现什么问题，主要是问题不难，方法也比较简洁，这次还是学到了很多方法，动态规划什么的，也算是了解了：）
原文：http://www.cnblogs.com/zzcs/p/5323534.html