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

陈尚涵

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

1. #include <iostream>
   
2. using namespace std;
   
3. int a[1000], b[1000];
   
4. int main(){
   
5.         int n;
   
6.         cin >> n;
   
7.         for (int i = 1; i <= n; i++){
   
8.                 cin >> a[i];
   
9.                 b[i] = b[i - 1] + a[i];
   
10.         }
    
11.         /*
    
12.         int max = -999;
    
13.         for (int i = 1; i <= n; i++){
    
14.                 for (int j = 1; j <= n - i + 1; j++){
    
15.                         int sum = 0;
    
16.                         for (int k = j; k <= j + i; k++){
    
17.                                 sum += a[k];
    
18.                         }
    
19.                         if (sum > max){
    
20.                                 max = sum;
    
21.                         }
    
22.                 }
    
23.         }
    
24.         */
    
25.         int max = -999;
    
26.         for (int i = 1; i <= n; i++){
    
27.                 for (int j = 1; j <= n - i + 1; j++){
    
28.                         int sum = b[j + i] - b[j - 1];
    
29.                         if (sum > max){
    
30.                                 max = sum;
    
31.                         }
    
32.                 }
    
33.         }
    
34.         cout << max;
    
35.         return 0;
    
36. }

复制代码

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

最佳答案

月排行榜 / 总排行榜

高山

2023-6-28 18:44:37

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

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

修改后的代码如下：

1. int max = -999;
   
2. for (int i = 1; i <= n; i++){
   
3.     for (int j = 1; j <= n - i + 1; j++){
   
4.         int sum = b[j + i - 1] - b[j - 1];
   
5.         if (sum > max){
   
6.             max = sum;
   
7.         }
   
8.     }
   
9. }
   
10. cout << max;
    

复制代码

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

跳转到最佳答案楼层

高山

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

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

修改后的代码如下：

1. int max = -999;
   
2. for (int i = 1; i <= n; i++){
   
3.     for (int j = 1; j <= n - i + 1; j++){
   
4.         int sum = b[j + i - 1] - b[j - 1];
   
5.         if (sum > max){
   
6.             max = sum;
   
7.         }
   
8.     }
   
9. }
   
10. cout << max;
    

复制代码

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

陈尚涵

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

...

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