[已解决]为什么暴力能满分，前缀和就不能满分呢？

陈尚涵

这边我在一个小oj上刷题
然后就找到了一到求一个数组中最大连续部分和的题目
心想，好一个简单的练习前缀和的题目！由于前缀和的解法与暴力差不多，所以我就先写的暴力，然后就直接ac了
接下来我尝试用前缀和做，代码是这样的（注释部分代表暴力），结果呢，70分

#include <iostream>
using namespace std;
int a[1000], b[1000];
int main(){
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++){
                cin >> a[i];
                b[i] = b[i - 1] + a[i];
        }
        /*
        int max = -999;
        for (int i = 1; i <= n; i++){
                for (int j = 1; j <= n - i + 1; j++){
                        int sum = 0;
                        for (int k = j; k <= j + i; k++){
                                sum += a[k];
                        }
                        if (sum > max){
                                max = sum;
                        }
                }
        }
        */
        int max = -999;
        for (int i = 1; i <= n; i++){
                for (int j = 1; j <= n - i + 1; j++){
                        int sum = b[j + i] - b[j - 1];
                        if (sum > max){
                                max = sum;
                        }
                }
        }
        cout << max;
        return 0;
}

这边循环的话i是长度，j是起始下标，k是为了求和
这个我觉得没有问题啊，是我的代码哪里有问题还是oj有问题啊

最佳答案

月排行榜 / 总排行榜

高山

2023-6-28 18:44:37

根据你提供的代码，前缀和部分的实现看起来是正确的。然而，有一个细微的错误可能导致得到错误的结果。

在第二个循环中，内层循环的起始下标应该为j，终止下标应该为j+i-1，而不是j+i。这是因为数组的下标从1开始，而不是0。

修改后的代码如下：

int max = -999;
for (int i = 1; i <= n; i++){
    for (int j = 1; j <= n - i + 1; j++){
        int sum = b[j + i - 1] - b[j - 1];
        if (sum > max){
            max = sum;
        }
    }
}
cout << max;

请尝试修改代码并重新提交，看是否能够得到正确的结果。如果问题仍然存在，请检查其他部分代码是否有问题，或者考虑联系OJ平台的管理员以获取更多帮助。
若有疑问，请继续提问！

跳转到最佳答案楼层

高山

根据你提供的代码，前缀和部分的实现看起来是正确的。然而，有一个细微的错误可能导致得到错误的结果。

在第二个循环中，内层循环的起始下标应该为j，终止下标应该为j+i-1，而不是j+i。这是因为数组的下标从1开始，而不是0。

修改后的代码如下：

int max = -999;
for (int i = 1; i <= n; i++){
    for (int j = 1; j <= n - i + 1; j++){
        int sum = b[j + i - 1] - b[j - 1];
        if (sum > max){
            max = sum;
        }
    }
}
cout << max;

请尝试修改代码并重新提交，看是否能够得到正确的结果。如果问题仍然存在，请检查其他部分代码是否有问题，或者考虑联系OJ平台的管理员以获取更多帮助。
若有疑问，请继续提问！

陈尚涵

高山 发表于 2023-6-28 19:20
根据你提供的代码，前缀和部分的实现看起来是正确的。然而，有一个细微的错误可能导致得到错误的结果。

...

懂了，但还是不知道为啥暴力可以过