Как эта функция C++ работает иначе, чем эквивалентная функция Java?

Question

Я пытаюсь реализовать версию Java следующего алгоритма C++:

void constructPrintLIS(int arr[], int n)
{
    std::vector< std::vector<int> > L(n);

    L[0].push_back(arr[0]);

    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if ((arr[i] > arr[j]) &&
                (L[i].size() < L[j].size() + 1))
            {
                L[i] = L[j];
                cout << true << endl;
            }
            else
            {
                cout << false << endl;
            }
        }

        L[i].push_back(arr[i]);
    }

    std::vector<int> max = L[0];

    for (std::vector<int> x : L)
    {
        if (x.size() > max.size())
        {
            max = x;
        }
    }

    printLIS(max);
}

Вот версия Java

private static List<Integer> getLongestIncreasingSubsequence(
        List<Integer> sequence
        )
{   
    ArrayList<ArrayList<Integer>> cache = 
            new ArrayList<ArrayList<Integer>>(sequence.size());
    // Populate the elements to avoid a NullPointerException
    for(int i = 0; i < sequence.size(); i++)
    {
        cache.add(new ArrayList<Integer>());
    }
    cache.get(0).add(sequence.get(0));

    // start from the first index, since we just handled the 0th
    for(int i = 1; i < sequence.size(); i++)
    {
        // Add element if greater than tail of all existing subsequences
        for(int j = 0; j < i; j++)
        {
            if((sequence.get(i) > sequence.get(j)) 
                    && (cache.get(i).size() < cache.get(j).size() + 1))
            {
                cache.set(i, cache.get(j));
            }
        }
        cache.get(i).add(sequence.get(i));                  
    }

    // Find the longest subsequence stored in the cache and return it
    List<Integer> longestIncreasingSubsequence = cache.get(0);
    for(List<Integer> subsequence : cache)
    {
        if(subsequence.size() > longestIncreasingSubsequence.size())
        {
            longestIncreasingSubsequence = subsequence;
        }
    }
    return longestIncreasingSubsequence;
}

Я не понимаю, что я делаю по-другому. Алгоритм C++ выводит правильный результат, когда тестовая последовательность {9766, 5435, 624, 6880, 2660, 2069, 5547, 7027, 9636, 1487}с правильным результатом 624, 2069, 5547, 7027, 9636, Однако версия Java, которую я написал, возвращает неверный результат 624, 6880, 2660, 2069, 5547, 7027, 9636, 1487 и я не понимаю почему. Я попытался отследить это в отладчике, и я не могу понять, что происходит не так.

Я попытался добавить оператор печати, указывающий, оценивал ли оператор if значение true / false каждый раз, и сравнил его с программой на C++, и это было то же самое, так что это не проблема.

Я подозреваю, что это как-то связано с тонкой разницей между вектором и ArrayList, но я не знаю.

Answer 1

Я подозреваю, что проблема в том, что в Java кеш содержит ссылки на списки, тогда как в C++ он содержит сами списки.

Таким образом, в C++

L[i] = L[j];

копирует список по указателю j индексировать iтогда как в Java

cache.set(i, cache.get(j));

копирует ссылку. Это означает, что когда вы впоследствии добавляете элементы к одному, они также добавляются к другому.

Может быть, использовать

cache.set(i, new ArrayList<>(cache.get(j)));

так что вы создаете копию, как в C++.