Нам дан массив со всеми a [ i ] > 0 .
Теперь нам нужно найти сколько различных сумм могут быть сформирована из ее подрешеток (где подмассив представляет собой непрерывный диапазон массива, т.е. [ J ... K ] для некоторого J , к , сумма является суммой всех из элементы подмассива). Например, если a = [ 1 , 2 , 1 ] , то ответ 4: мы можем сформировать 1 , 2 , 3 , 4 .
Я знаю, как подсчитать количество разных сумм за времени.
Кроме того, я пришел к выводу, что это похоже на классическую проблему, где нам нужно найти количество различных подстрок строки. Я думал о возможности построения суффиксного массива и его решения аналогичным образом (за раз). Но я не смог понять, как изменить это, чтобы работать здесь. Например, если мы используем суффиксный массив для a = [ 1 , 2 , 1 ], мы получим 5 случаев вместо четырех приемлемых. Возможно ли это сделать с помощью массивов суффиксов или я не в том направлении?
Также есть еще одно направление, о котором я думал. Разделяй и властвуй. Например, если я делю массив на две части каждый раз, пока он не сводится к одному элементу. Один элемент может иметь одну сумму. Теперь, если мы объединяем два отдельных элемента, это можно сделать двумя способами: если оба отдельных диапазона имеют один и тот же элемент, мы получаем 2 разные суммы, или если оба имеют разные элементы, мы получаем 3 разные суммы. Но я не могу обобщить это для объединения массивов длиной больше 1. Можно ли объединить два массива размера m и получить ответ в ?
источник
Ответы:
«Почти наверняка» связано с тем, что проблема не требует значений сумм в качестве выходных данных. Тем не менее, я не думаю, что дубликатов можно избежать без определения хотя бы большинства значений.
источник