c - 算法出现问题，但不知道错那里了？

问题描述

问 题

算法要求是：https://pta.patest.cn/pta/test/558/exam/4/question/7400

我的算法是：

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

这篇关于c - 算法出现问题，但不知道错那里了？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！