我的算法是:
#include <stdio.h>
int main()
{
int n;
scanf("%d", &n);
int a[n];
int i, j, k, h;
int q = 0;
for (i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
int max;
max = 0;
j = 0;
k = a[0];
h = a[n - 1];
for (i = 0; i < n; i++) {
if (a[i] >= 0) {
q = 1;
}
j = j + a[i];
if (j < a[i]) {
j = a[i];
if ((j > max) || ((j == max) && (j == 0))) {
k = a[i];
}
}
if (j > max) {
max = j;
h = a[i];
}
}
if (max == 0 && q == 1) {
k = 0;
h = 0;
}
if (q == 0) {
max = 0;
k = a[0];
h = a[n - 1];
}
//printf("%d\n", j);
printf("%d %d %d", max, k, h);
return 0;
}
提交时总是出现错误:
验证了好多数据也不知道错哪了,该怎么改,求大神指导。
#include <stdio.h>
int main() {
int maxSum, i, j, curSum, curI, n, k;
scanf("%d", &n);
int nums[n];
for (k = 0; k < n; k++) {
scanf("%d", &nums[k]);
}
maxSum = -1; // 子序列最大和
i = nums[0]; // 具有最大和的子序列起始与结束元素的值
j = nums[n - 1];
curSum = 0; // 当前子序列的和
curI = nums[0]; // 当前子序列起始元素的值
for (k = 0; k < n; k++) {
// 若当前子序列的和小于0则直接丢弃,以当前元素为起点重新开始
if (curSum < 0) {
curSum = curI = nums[k];
} else { // 否则继续求和
curSum += nums[k];
}
// 当前子序列的和计算完毕后,与之前已保存的最大子序列的和
// 比较,如果较大就更新之,同时更新起始和结束元素的值
if (curSum > maxSum) {
maxSum = curSum;
i = curI;
j = nums[k];
}
}
// 这个判断用来检查是否所有元素都是负值(这也是将maxSum初始化为-1的原因)
if (maxSum < 0) {
maxSum = 0;
}
printf("%d %d %d", maxSum, i, j);
return 0;
}
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。