Решение для динамического программирования не работает в среде Hackerrank

Вопрос:

Мой код отлично работает на моей машине, но он терпит неудачу даже в примерах тестов на Hackerrank. Как один и тот же код может давать разные результаты в двух разных средах?

 #include <bits/stdc  .h>
#include <algorithm>
using namespace std;

int maxum(int arr[], int n)
{
    int t[100][100];
    for(int i=0;i<n 1; i  )
        for(int j=0; j<n 1;j  )
        {
            if(i==0)
                t[i][j]=0;
            else
                t[i][j]=max(t[i-1][j] arr[i-1], t[i-1][j] );
        }
    int maximum=0;
    for(int i=0;i<n 1;i  )
    for(int j=0; j<n 1;j  )
    {
        if(t[i][j]>maximum)
        maximum=t[i][j];
    }
    return maximum;
}


int main()
{
    int arr[100],i,n;
    cin>>n;
    for(i=0;i<n;i  )
        cin>>arr[i];
    cout<<maxum(arr,n);
    return 0;
}

1. Можете ли вы рассказать нам, каков один из простых тестовых примеров? Это сэкономит много времени, если вы сможете.

2. Также может помочь объяснить, что должен делать код.

3. Что, если n равно 99?

4. В какой ссылке C говорится об использовании нестандартного включаемого файла bits/stdc .h ? Вашему коду нужно только #include <iostream> ; использование двух других является пустой тратой времени на сборку.

5. К вашему сведению, использование описательных имен переменных оказывает незначительное влияние на процесс сборки, но затрудняет чтение кода. У вас есть по крайней мере 26 ^ 32 возможных комбинации букв для имен переменных, поэтому используйте более описательные имена.

Ответ №1:

Алгоритм просто неправильный. Например, учитывая входные данные из первого тестового примера

 5
3 7 4 6 5

Правильный ответ — 13 (7 6), но ваш код выводит 25 (3 7 4 6 5).

Похоже, не реализовано требование, чтобы члены максимального подмножества были несмежными.

1. Я запустил те же тестовые примеры в моем Dev C , и он выдал 13 в качестве выходных данных. Что здесь происходит?

2. Понятия не имею. Вот мой тестовый пример godbolt.org/z/fbGaKn

3. На самом деле я написал его рекурсивную версию и, имея небольшие знания о DP, попытался преобразовать ее в это. Это действительно работало на моей машине, но здесь оно показывает разные ответы. Можете ли вы попробовать запустить его на своем компьютере и проверить?

4. Я не понимаю. Значит, разработчики C ошибочны?

5. @cyberhawk Я только что запустил код на своем локальном компьютере, тот же неверный результат, 25.

Ответ №2:

Ваш код демонстрирует неопределенное поведение, по крайней мере, для больших входных данных. Пример:

 g   -O3 -Wall -Wextra -pedantic -std=c  17 -fno-exceptions -fsanitize=address a.cpp
yes 100 | ./a.out

Вызывает жалобу asan, хотя входные данные действительны в соответствии с ограничениями, указанными в предоставленной вами ссылке.

 ==298664==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7ffce142a650 at pc 0x55697440f74d bp 0x7ffce14209c0 sp 0x7ffce14209b8
WRITE of size 4 at 0x7ffce142a650 thread T0
    #0 0x55697440f74c in maxum(int*, int) (/tmp/a.out 0x174c)
    #1 0x55697440f26c in main (/tmp/a.out 0x126c)
    #2 0x7fc97926acc9 in __libc_start_main ../csu/libc-start.c:308
    #3 0x55697440f3a9 in _start (/tmp/a.out 0x13a9)

[rest of asan output omitted]