c++ - 我需要一个测试用例来证明我的算法/代码是错误的

Question

我正在编写一个程序，用于查找总和最接近 0 的最大长度子数组。 其实我想解决这个问题:http://opc.iarcs.org.in/index.php/problems/DEVIOUS ，但是当我提交我的代码时，它只对 50% 的测试用例给出了正确答案。 我的代码运行良好，甚至为我自己的测试用例给出了正确的答案，所以我需要一个测试用例来证明我的代码/算法是错误的，这样我才能找到我的代码中的错误。

这是我的算法，

1. Create an array 'temp' equal to the size of the input array, initialize all the elements of temp such that, temp[i] = sum of all elements up to input[i]
2. Sort the array temp, find 'i' in temp such that temp[i-1] - temp[i] is closest to 0

这是我解决上面链接问题的代码。

#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <limits.h>

using namespace std;

struct element{
    int index;
    int value;
};

bool compare(element a, element b){
    return a.value < b.value;
}

int main(){
    int n;
    cin >> n;
    int array [n];
    element elements[n];
    int sum = 0;

    for(int i = 0 ;i < n; i ++){
        cin >> array[i];
        sum = sum + array[i];
        elements[i].index = i;
        elements[i].value = sum;
    }

    sort(elements,elements+n,compare);

    int diff = INT_MAX;
    int i1 = 0,i2 = 0;
    for(int i = 1;i < n;i ++){
        int temp = elements[i].value - elements[i-1].value;
        if(temp < diff){
            diff = temp;
            i1 = elements[i].index;
            i2 = elements[i-1].index;
        }
        else if(temp == diff){
            if(abs(elements[i].index - elements[i-1].index) > abs(i1-i2)){
                i1 = elements[i].index;
            i2 = elements[i-1].index;
            }
        }
    }

    diff = 0;
    int s,e;
    if(i1 >= i2){
        e = i1, s = i2+1;
    }else{
        s = i1+1, e = i2;
    }

    for(int i = s;i <= e ; i++){
        diff = diff+array[i];
    }
    cout << diff << endl;

    cout << s+1 << " " << e+1;

    return 0;
}

编辑:我在我的代码中发现了一个错误并对其进行了编辑，它现在为 80% 的输入给出了正确答案

Answer 1

In other words, if the profits/losses at the stations are p1, p2, ..., pN the minister would like to handover a sequence i, i+1, ..., j such that the absolute value of pi + pi+1 + ... + pj is minimized. If there is more than one sequence with this minimum absolute value then he would like to hand over the longest one

我认为你的算法有点错误:

temp[i] = sum of all elements up to input[i] Sort the array temp

序列的开始位置很可能不是数组的开始位置 - 它可以是一个子序列，不要忘记。

-1 | -2 | 10 | 5 |-10 | 6

   |    |    | x | x  | x

edit2:删除了错误的解释，现在我看了代码 -

if(temp < diff){
        diff = temp;
        i1 = elements[i].index;
        i2 = elements[i-1].index;
    }

您确实偏爱 -ve 个数字(损失)。可能是因为它略小于 -ve 或 +ve(但 abs 值较小)，所以未命中数更接近零？