首页 > 代码库 > 【编程之美】2.14 求数组的子数组之和的最大值
【编程之美】2.14 求数组的子数组之和的最大值
做过的，就说下思路。
用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;}
【编程之美】2.14 求数组的子数组之和的最大值
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。