Разбить список целых чисел на подсписки равной суммы за линейное время

Question

Я нашел алгоритм для этого следующим образом:

1. По заданному списку l вычислить его сумму s.
2. Рассчитать следующую таблицу:

(s, Acc)

1. (с, 0)
2. (s-x1, x1)

3. (s-x1-x2, x1 + x2)

   ...

п. (S-x1 -... x_n-1, x1 + x2 + ... + x_n-1)

в то время как на каждом шаге вы проверяете, равен ли левый элемент пары второму.

Затем этот алгоритм определяет за линейное время, можно ли разбить ваш список на два подсписка, чтобы каждый подсписок суммировал одинаковую величину.

Я некоторое время пытался доказать это формально. Однако я начинаю думать, что это может быть допустимо только для натуральных чисел, а не для целых чисел.

1. Можете ли вы подтвердить это мнение?
2. Можете ли вы дать алгоритм для этого для целых чисел и для линейной сложности?

Редактировать (мое решение до сих пор)

fun check_list :: "int list ⇒ int ⇒ int ⇒ bool" where
"check_list [] n acc = False" |
"check_list (x#xs) n acc = (if n = acc then True else (check_list xs (n-x) (acc+x)))"

fun linear_split :: "int list ⇒ bool" where
"linear_split [] = False" |
"linear_split [x] = False" |
"linear_split (x # xs) = check_list xs (sum_list xs) x" 

Answer 1

Вам предлагается разделить список (как он есть) на две части без изменения порядка элементов.

Я некоторое время пытался доказать это формально.

Ваш алгоритм правильный, так как вы в основном покрываете каждое возможное разделение , перемещая разделитель по списку:

 | O O O  split 1
 O | O O  split 2
 O O | O  split 3
 O O O |  split 4

Можете ли вы дать алгоритм для этого для целых чисел и для линейной сложности?

Ваш алгоритм работает и для целых чисел. Опять же, потому что вы проверяете каждое возможное решение, а его сложность линейна, поскольку вы просто перебираете список дважды (в первый раз для вычисления sum)