А какой-то конкретный раздел можете подсказать? Велосипед нужен исключительно в образовательных целях и практике реализации. Проблема, как я уже сказал в том, что я не понимаю, как переводить число из двоичной системы в десятичной при ограниченном размере стандартного числового типа.
Спасибо вам за совет! Вроде как разобрался, дополнительно используя описание проблемы о разбиении. А разве не получится без использования дополнительного массива prev восстановить ответ? Ведь у нас же есть последовательности в массиве M[n, S, S] для элементов, которые входят либо в разбиение S1, либо в S2. Просто их вычеркиваем из входного массива, получаем два разбиения, а оставшееся разбиение - то что осталось. )
Спасибо за ответ. Только я не очень понимаю, каким образом у Вас заполняются массивы d и prev.
Насколько я понял, изначально d заполнен как-то так d = [-1, inf, inf..... inf], prev также. Для 1 мы используем двоичный поиск по d и видим, что можем вставить элемент на 1 позицию. Записываем в d[1] = 0, prev[j - 1] = -1, так как предыдущего нет. Для 2 видим, что можно вставить её на 2 позицию, обновляем d и prev соответственно. Но дальше я теряю нить рассуждений, так как не понимаю, что делать дальше. У вас в массиве d хранятся {-1,0,1,7,6,4,-1,-1,-1,...}, но это не является правильной подпоследовательностью, т. к. элемент с индексом 7 < чем элемент с индексом 6.