SEG FAULT w wyznaczeniu maksymalnej sumy C++

Question

Cześć,

Na themisie mam zadanie, które przechodzi mi w 1 na 2 egzaminy, 2 wywala mi seg fault. Normalnie pddaję się już, nie wiem, o co chodzi.

Treść zadania jest następująca:

Dla danej planszy liczb nieujemnych podaj maksymalną sumę liczb, jaką można zebrać idąc z lewego narożnika (na górze) do prawego (na dole) w taki sposób, że dozwolone są tylko ruchy w dół lub w prawo.

Wejście
W pierwszej linii wejścia dana jest liczba testów. Każdy test rozpoczyna się dwoma liczbami h, w (1 ≤ h, w ≤ 1000) zadającymi liczbę wierszy i kolumn planszy. Następnie dana jest plansza o tychże wymiarach wypełniona liczbami co do modułu nie większymi od miliona.

Wyjście
Dla każdego testu należy wypisać jedną liczbę – odpowiedź zgodną z opisem w zadaniu.

Przykład
Dla danych wejściowych

2

2 3
1 7 9
2 8 4

3 4
1 1 1 1
2 3 1 7
1 1 2 8
poprawną odpowiedzią jest
21
22

Po czy mój kod:

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

struct TAB
{
    int val1, val2, vals, valt;
    int tab[1000];

};

int getSum(int BITree[], int index)
{
    int sum = 0;
    while (index > 0) {
        sum = max(sum, BITree[index]);
        index -= index & (-index);
    }
    return sum;
}

void updateBIT(int BITree[], int newIndex,
               int index, int val)
{
    while (index <= newIndex) {
        BITree[index] = max(val, BITree[index]);
        index += index & (-index);
    }
}

int maxSumIS(int arr[], int n)

{
    int newindex = 0, max_sum;

    map<int, int> uniqueArr;

    for (int i = 0; i < n; i++) {
        uniqueArr[arr[i]] = 0;
    }

    for (map<int, int>::iterator it = uniqueArr.begin();
         it != uniqueArr.end(); it++) {

        newindex++;

        uniqueArr[it->first] = newindex;
    }


    int* BITree = new int[newindex + 1];

    for (int i = 0; i <= newindex; i++) {
        BITree[i] = 0;
    }

    for (int i = 0; i < n; i++) {
        max_sum = getSum(BITree, uniqueArr[arr[i]] - 1);

        updateBIT(BITree, newindex,
                 uniqueArr[arr[i]], max_sum + arr[i]);
    }

    return getSum(BITree, newindex);
}


int main()
{
    int num;
    cin >> num;
    if ((num<1) || (num > 1000))
    {
        return 0;
    }
    TAB stokrotki[num];
    for(int i = 0; i < num; i++)
    {
        cin >> stokrotki[i].val1;
        cin >> stokrotki[i].val2;
        stokrotki[i].vals = stokrotki[i].val1 * stokrotki[i].val2;
        stokrotki[i].valt = stokrotki[i].vals + 2;
        stokrotki[i].tab[0] = stokrotki[i].val1;
        stokrotki[i].tab[1] = stokrotki[i].val2;
        for(int j=2; j<stokrotki[i].valt; j++)
        {
            cin >> stokrotki[i].tab[j];
            if((stokrotki[i].tab[j] > 1000000))
            {
                return 0;
            }
        }

    }
    for(int i = 0; i < num; i++)
    {
        int arr[stokrotki[i].valt];
        for(int j=0; j<stokrotki[i].valt;j++)
        {
            arr[j] = stokrotki[i].tab[j];
        }
        int n = sizeof(arr) / sizeof(arr[0]);
        cout << maxSumIS(arr, n) << endl;
    }

    return 0;
}

 

No dla przykładu z zadania śmiga jak złoto - dla sprawdzianu 1 - złoto , ale sprawdzian 2 kicha.

Czy ktoś byłby w stanie wykryć co zrobiłem nie tak i pokazać w którym miejscu należy poprawić?

Answer 1

1. Masz wyciek pamięci - nigdzie nie usuwasz  tablicy utworzonej za pomocą operatora new.
2. Sam algorytm zawarty w funkcji maxSumIS zwraca błędne rezultaty - nigdzie nie widzę aby wykorzystywana była w nim informacja na temat wymiarów planszy.
3. Tworzysz tablice typu VLA co nie jest dobrym pomysłem w języku C++ ( tylko niektóre kompilatory na to pozwalają ) - zmień je na dynamiczne lub użyj std::vector.