У меня такой вопрос:
Учитывая следующее:
A = [9,6,9,3,8,9,2,0,4,12] C = [r,g,r,g,r,g,r,r,r,g]
Где - r = красный - g = зеленый
Этот список представляет цвет числа в том же индексе в массиве A т.е. A[0] = 9 = red, A[1] = 6 = green, ...
Нам нужно выбрать число N для начала, если число green мы можем двигаться только вправо (на любые числа) к числу, которое на >=N больше текущего.
Если число N равно red, мы можем перемещаться только влево (на любое числа) на число, которое на >=N больше текущего.
Цель : найти самую длинную возможную последовательность ходов, вернуть индексы пути. Если есть несколько подпоследовательностей одинаковой длины, которые являются самыми длинными, вернуть кого угодно:
Пример 1:
A = [9,6,9,3,8,9,2,0,4,12]
C = [r,g,r,g,r,g,r,r,r,g]
output: [7,6,3,8,1,4,0]
Пример 2:
A = [1,2,3,4,5,6,7,10]
C =[r,r,r,r,r,r,r,r]
output:[7]
Пример 3:
A = [5,3,2,0,24,9,20]
C = [g,g,g,g,r,r,g]
output: [0,5,4]
Текущая идея моего алгоритма:
Рассмотрим возможные ходы для каждого элемента в A, для первого примера A[0] = 9 = red.
Так как левых элементов нет, есть только 1 ход (выберите A[0]).
Итак, OPT[0] = 1. Для A[1] = 6 = green. Возможные ходы: A[2]= 9, A[4] = 8, A[5] = 9, A[9] =12.
Рекурсия - OPT[i] = max{1, 1+ OPT[j]}, где j - следующий возможный ход.
На правильном ли я пути, используя динамическое c программирование? Время выполнения O(n²) не так ли?