开发者社区> 问答> 正文

算法错了,但不知道错那里了?

2
我的算法是:

#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;
 } 

提交时总是出现错误:
3

验证了好多数据也不知道错哪了,该怎么改,求大神指导。

展开
收起
杨冬芳 2016-05-30 18:21:34 2147 0
1 条回答
写回答
取消 提交回答
  • IT从业
    #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;
     }

    4

    2019-07-17 19:20:55
    赞同 展开评论 打赏
问答分类:
问答地址:
问答排行榜
最热
最新

相关电子书

更多
低代码开发师(初级)实战教程 立即下载
冬季实战营第三期:MySQL数据库进阶实战 立即下载
阿里巴巴DevOps 最佳实践手册 立即下载