那个,是sum小于0的时候令sum等于0吧?而且判断应该提到前面
//Version 1.0
int max_sum(int* a, size_t sz) {
int max = 0, sum = 0, maxOfAll = 0;
for (int j = 0; j < sz; ++j) {//通过两次循环来遍历所有子序列和
for (int i = j; i < sz; ++i) {
sum += a[i];
if (sum > max)
max = sum;
}
if (max > maxOfAll)
maxOfAll = max;
sum = 0;
}
return maxOfAll;
}
copy
//Version 2.0
int max_sum(int* a, size_t sz) {
int max = 0, sum = 0;
for (int i = 0; i < sz; ++i) {
sum += a[i];
if (sum > max)
max = sum;
if (sum < 0)// 和为负则抛弃其和,重新计算
max = 0;
}
return max;
}
copy
刚开始的想法很直观,就是遍历所有的子序列和,然后求最大值。跑了几遍发现这样效率很低,算法时间复杂度为O(n!)。后来看了别人的实验报告, 原来可以通过循环中判断和的值是否为负,如果为负则把子序列和重置巧妙地减小复杂度,改过之后的函数Version2 中所示,此时算法时间复杂度为O(n),可见有很大的提升。
copy
学习时间 57分钟
操作时间 15分钟
按键次数 111次
实验次数 3次
报告字数 690字
是否完成 完成