3

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

这是我的算法，

  1. 创建一个等于输入数组大小的数组“temp”，初始化 temp 的所有元素，使得 temp[i] = 直到 input[i] 的所有元素的总和
  2. 对数组 temp 进行排序，在 temp 中找到“i”，使得 temp[i-1] - temp[i] 最接近 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% 的输入提供了正确的答案

4

1 回答 1

1

换句话说，如果车站的利润/损失是 p1, p2, ..., pN，部长想要移交一个序列 i, i+1, ..., j 使得 pi + pi 的绝对值+1 + ... + pj 被最小化。如果有不止一个具有这个最小绝对值的序列，那么他想交出最长的一个

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

temp[i] = 直到 input[i] 的所有元素的总和 对数组 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 值更小）？

于 2012-11-05T10:11:01.540 回答