【编程之美】2.14 求数组的子数组之和的最大值
浏览数：15 /
时间：2015年06月08日
做过的，就说下思路。
用Sum记录A[0...N-1]中 以第i个元素结尾的子数组中的最大和，
若以第i-1个元素结尾的子数组小于0，那么以第i个元素结尾的子数组中的最大和就是 A[i]本身 否则是A[i] + Sum(i-1的)
总结起来就是 Sum = (Sum > 0) ? A[i] + Sum : A[i]；
再记录下所有出现过的Sum中最大的值就可以了。
#include <stdio.h> int getMaxSubArraySum(int * a, int alen) { int maxSum = a[0]; int Sum = a[0]; for(int i = 1; i < alen; i++) { Sum = (Sum > 0) ? Sum + a[i] : a[i]; maxSum = (Sum > maxSum) ? Sum : maxSum; } return maxSum; } int main() { int a[7] = {-2,5,3,-6,4,-8,6}; int b[6] = {1,-2,3,5,-3,2}; int c[6] = {0,-2,3,5,-1,2}; int d[5] = {-9,-2,-3,-5,-3}; int max = getMaxSubArraySum(d, 5); return 0; }
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
