Комментарии 2
Хорошая статья. В отличии от многих статей про алгоритмы на хабре тут действитеньно объясняется "как" и "почему" а не "что", и статья не является лишь текстовой копией кода в стиле:
// Если значение отрицательное
if (x < 0) {
y = 0; // Присваеваем 0
}Единественное замечаение: стоило бы заострить внимание, почему в последней версии сравниваются second_array[k] и first_array[i], ведь до этого сравнивались 2 значения в second_array.
Благодарю за комментарий! Вы правы, этот момент я несколько замял под ковёр.
В предпоследней версии сравнение second_array[l] < second_array[j] используется для поддержания возрастания подпоследовательности, однако в этом случае можно сравнивать и second_array[l] < first_array[i], т.к. внутри этого блока элементы первого и второго массивов равны.
В последней версии при заполнении строки i любой элемент second_array будет сравниваться с first_array[i] на равенство. То есть при равенстве first_array[i] == second_array[j] неравенства first_array[i] > second_array[k] и second_array[j] > second_array[k] будут эквивалентны. Поэтому, достаточно сравнения с first_array[i], потому что при встрече равного элемента из второго массива мы будем уверенны в возрастании подпоследовательности.
Надеюсь, что смог подробнее объяснить этот момент!
Наибольшая общая возрастающая подпоследовательность