В этой задаче нельзя обойтись "текущей подпоследовательностью". Надо держать самые длинные подпоследовательности, заканчивающиеся на разные элементы (чем больше элемент, тем длиннее должна быть подпоследовательность, заканчивающаяся на него), и когда приходит новый элемент, то присоединить его к самой длинной из последовательностей, к какой возможно (причём старую последовательность сразу выбрасывать нельзя - она ещё может пригодиться), а потом выбросить неоптимальные (последовательность такой же длины, что и другая, но заканчивающаяся на больший элемент).
Например, для последовательности [1,2,7,8,9,5,6,3] вам придётся помнить
[1,2,7,8,9]
[1,2,5,6]
[1,2,3]
[1,2]
[1]
Любая из этих последовательностей может быть началом правильного ответа.
Так что начало решения у вас правильное. Но в векторе d должны храниться не числа, а их индексы (и поиск должен быть более сложным), а массив prev надо модифицировать так: prev[i]=d[j-1].
Для примера [1,2,7,8,9,5,6,3] получаем
d={-1,0,1,7,6,4,-1,-1,-1,...}, prev={-1,0,1,2,3,1,5,1}
(значение -1 используется для обозначения ситуации "нет такого индекса").