Question

C语言求最长子序列

代码如下

#include <stdio.h>
int main() {
int count, i, k, a[100] = {0}, b[10000] = {0}, n, num, max = 0, q, m, j;
scanf("%d", &n);
for (count = 0; count < n; count++) {
scanf("%d", &num);
for (i = 0; i < num; i++) scanf("%d", &a[i]);
k = 0;
for (i = 0; i < num; i++)
for (q = 1; q < num + 1; q++) {
for (m = i; m < i + q; m++)
b[k] += a[m];
k++;
}
j = k - 1;
max = b[j];
for (; j >= 0; j--)
if (max < b[j]) max = b[j];
printf("%d\n", max);
max = 0;
for (i = 0; i < 10000; i++) b[i] = 0;
}
return 0;
}
用的是穷举，但是测试结果中上一个长数据还是会对下一个较短数据产生影响，难道是b数组没清零吗？还是我的清零方法有问题？求教
说错了 是求最大子序列 如果全为负应该是找最大的负数

Answer 1

下面是你的代码修改过后的结果，改过的地方都有注释，另有测试样例。
#include <stdio.h>
/*
5
5
-2 5 4 -7 3
最长子序列：9
4
-2 -3 8 -7
最长子序列：8
3
-2 -2 7
最长子序列：7
2
-1 5
最长子序列：5
1
-2
最长子序列：0

Process returned 0 (0x0) execution time : 30.999 s
Press any key to continue.

*/
int main() {
int count, i, k, a[100] = {0}, b[10000] = {0}, n, num, max = 0, q, m, j;
scanf("%d", &n);
for (count = 0; count < n; count++) {
scanf("%d", &num);
for (i = 0; i < num; i++) scanf("%d", &a[i]);
k = 0;
for (i = 0; i < num; i++)
for (q = 1; q < num + 1; q++) {
for (m = i; (m < i + q) && (m < num); m++) //在这里再加一个判断条件(m < num)，
b[k] += a[m];
k++;
}
j = k - 1;
max = 0; //如果全部都是负数的话，结果应该是0，即一个都不选
for (; j >= 0; j--)
if (max < b[j]) max = b[j];
printf("最长子序列：%d\n", max);
max = 0;
for (i = 0; i < 10000; i++) b[i] = 0;
}
return 0;
}

追问

谢谢，加了一个m 小于num就过了，可是为什么呢

追答

因为如果下次的输入长度比上次短的话，一旦越界加的就是上次输入的值。
还有个方法就是在最前面你对所有的a的空间赋值为0.