Я решил подумать над задачкой и кое-что придумал. Проверять лень. Короче,

Question

Я решил подумать над задачкой и кое-что придумал. Проверять лень. Короче,

Начинать с целого массива и постепенно сужать его границы двуг к другу. Для этого нужно хранить суммы элементов по краям и указатели на воображаемые внутренние границы, которые на каждой итерации сдвигаются на 1 к середине. Текущее левое значение прибавляется к левой сумме и, если сумма стала меньше нуля, значит идти влево от него быссмысленно. Зануляем сумму и переставляем левую границу на следующий за текущим. Аналогично для правой стороны. И так до тех пор, пока указатели не сойдутся. Тогда, сумма двух накопленных сумм даст сумму искомого подмассива, а указатели границ - сам подмассив. Получаем O(n) по времени и O(1) по памяти. Верно?

#c++ #embedded #programming #russian

0

17.10.2016