找到整数的最大连续总和在阵列

我有这个执行，这个程序的结果是100，但正确答案是103 是任何人都知道什么是错在这个实现或是否有更好的办法用于查找数组中整数的最大连续和？找到整数的最大连续总和在阵列

在此先感谢。

#include <stdio.h> 

int main(void) { 
int a[] = { -3, 100, -4, -2, 9, -63, -200, 55 }; 
int max_sum, temp_sum, i, n = 12, t; 
temp_sum = max_sum = a[0]; 
for (i = 1; i < n; i++) { 
    if (a[i] > 0) 
     temp_sum += a[i]; 
    else { 
     t = 0; 
     while (a[i] < 0 && i < n) { 
      t += a[i]; 
      i++; 
     } 
     if (temp_sum + t > 0) { 
      temp_sum = temp_sum + t + a[i]; 
      if (temp_sum > max_sum) 
       max_sum = temp_sum; 
     } else if (i < n) 
      temp_sum = a[i]; 
    } 
} 
if (temp_sum > max_sum) 
    max_sum = temp_sum; 
printf("Maximum Numbers is %d \n", max_sum); 
return 0; 
}

来源

2012-04-10 Elnaz

这里有smt怪异的，我把你的代码复制到CodeBlocks，结果是332？ – 2012-04-10 19:48:45

这是功课吗？你应该考虑使用递归。 – 2012-04-10 19:49:59

“最大连续数”是什么意思？你怎么能得到103？ – Saphrosit 2012-04-10 19:50:20

您没有使用正确的索引：

在这里看到演示：http://codepad.org/wbXZY5zP

int max_sum, temp_sum, i, n = 8, t; 
temp_sum = max_sum = a[0]; 
for (i = 0; i < n; i++) { 
    (...) 
}

来源

2012-04-10 19:54:58

so'n = 8'并且循环从0到7（所以'i = 0'作为开始） – 2012-04-10 19:58:47

我建议Kadane's algorithm。在C++会是这样的（未经测试）：

int maxSubarray(std::vector<int> a) { 
    int maxAll = 0, maxHere = 0; 
    for (size_t i = 0; i < a.size(); ++i) { 
     maxHere = std::max(a[i], maxHere + a[i]); 
     maxAll = std::max(maxAll, maxHere); 
    } 
    return maxAll; 
}

来源

2012-04-10 19:54:39 Skiminok

如果找最大连续总和不是从索引0开始，最简单的方法是有两个循环

int max_sum, temp_sum, i, n = 8, t; 
max_sum = a[0]; 
for (t = 0; t < n; t++) { 
    temp_sum = 0; 
    for (i = t; i<n; i++) { 
     temp_sum += a[i]; 
     if (temp_sum > max_sum) 
      max_sum = temp_sum; 
    } 
}

来源

2012-04-10 20:06:11

正如其他用户所指出的，您的实施指数不正确。但是，我认为有必要添加一个答案，指出如果所有值均为负值（最接近正值的数字不在第一位），则您的实现失败。

要快速解决这一问题将在情况下a[i] < 0 && temp_sum + t < 0分配温度和当增加一个检查 - 在最后else块。

} else if (i < n) { 
    temp_sum = a[i]; 
    if (temp_sum > max_sum) 
     max_sum = temp_sum; 
}

来源

2012-04-10 20:12:35

找到整数的最大连续总和在阵列

回答

相关问题