2 qq 28839381 qq_28839381 于 2015.07.12 22:05 提问

求一个数组的子数组之和的最大值

1 #include
2 #include
3 void f(int size, int a[size]);
4 int main(void)
5 {
6 int size = 7;
7 int a[7] = {-2, 5, 3, -6, 4, -8, 6};
8 f(size, a);
9 return 0;
10 }
11

12 void f(int size,int a[size])
13 {
14 int max = INT_MIN;
15 int i, j;
16 int sum = 0;
17 for(i=0;i 18 {
19 if(a[i] 20 for(j=i;j 21 {
22 sum = 0;
23 sum = sum +a[j];
24 max = (max > sum? max: sum);
25 }
26 }
27 printf("%d\n",max);
28 }

请问为什么运行的结果是6不是8?

3个回答

oyljerry
oyljerry   Ds   Rxr 2015.07.12 22:26

这个算法就是你每次求得的子数组和大于零时,你就保留继续加下一个。否则就放弃。重新开始。
基于这个原则。最大值发生在子数组5,3,-6,4。结果是6

oyljerry
oyljerry 回复qq_28839381: 如果有帮助,请采纳答案,谢谢
2 年多之前 回复
qq_28839381
qq_28839381 明白了,sum位置搞错了
2 年多之前 回复
caozhy
caozhy   Ds   Rxr 2015.07.12 23:06
CSDNXIAOC
CSDNXIAOC   2015.07.16 15:24

1  蛮力法:
   从第一个元素开始的子序列有A[0],A[0]-A[1],....A[0]-A[i],...A[0]-A[n-1]
   从第i个元素开始的子序列有]..A[i,A[i]-A[i+1],...A[i]-A[n]
   如此我们只需把每一种情况求出来进行比较即可得到结果
  第i个元素都是是N-i次计算
  共有N个元素 那么复杂度位 N-1+(N-2)+....1 =......
答案就在这里:求数组的子数组之和的最大值
----------------------你好,人类,我是来自CSDN星球的问答机器人小C,以上是依据我对问题的理解给出的答案,如果解决了你的问题,望采纳。

Csdn user default icon
上传中...
上传图片
插入图片