Подсчет количества сумм из смежных подмассивов массива

12

Нам дан массив со всеми a [ i ] > 0 .a[1n]a[i]>0

Теперь нам нужно найти сколько различных сумм могут быть сформирована из ее подрешеток (где подмассив представляет собой непрерывный диапазон массива, т.е. [ J ... K ] для некоторого J , к , сумма является суммой всех из элементы подмассива). Например, если a = [ 1 , 2 , 1 ] , то ответ 4: мы можем сформировать 1 , 2 , 3 , 4 .a[jk]j,ka=[1,2,1]1,2,3,4

Я знаю, как подсчитать количество разных сумм за времени.O(n2)

Кроме того, я пришел к выводу, что это похоже на классическую проблему, где нам нужно найти количество различных подстрок строки. Я думал о возможности построения суффиксного массива и его решения аналогичным образом (за раз). Но я не смог понять, как изменить это, чтобы работать здесь. Например, если мы используем суффиксный массив для a = [ 1 , 2 , 1 ], мы получим 5 случаев вместо четырех приемлемых. Возможно ли это сделать с помощью массивов суффиксов или я не в том направлении?O(n)a=[1,2,1]

Также есть еще одно направление, о котором я думал. Разделяй и властвуй. Например, если я делю массив на две части каждый раз, пока он не сводится к одному элементу. Один элемент может иметь одну сумму. Теперь, если мы объединяем два отдельных элемента, это можно сделать двумя способами: если оба отдельных диапазона имеют один и тот же элемент, мы получаем 2 разные суммы, или если оба имеют разные элементы, мы получаем 3 разные суммы. Но я не могу обобщить это для объединения массивов длиной больше 1. Можно ли объединить два массива размера m и получить ответ в ?O(m)

Salena
источник
O(n lg n)
Я бы предложил начать со следующей проблемы: насколько сложно решить, есть ли два интервала с одинаковой суммой? Соблазнительно доказать 3SUM-сложность этой проблемы, но пока я не смог.
Юваль Фильмус

Ответы:

2

O(n2)Θ(n2)

[1,2,4,8,,2n]n(n+1)2


«Почти наверняка» связано с тем, что проблема не требует значений сумм в качестве выходных данных. Тем не менее, я не думаю, что дубликатов можно избежать без определения хотя бы большинства значений.

FrankW
источник
Я не вижу особой причины, по которой не должно быть способа как-то избежать обхода всех возможностей, в то же время предлагая правильный ответ. Алгоритмы динамического программирования делают это регулярно.
Юваль Фильмус