понедельник, 27 октября 2008 г.

Поиск последовательности в массиве

Задача

Есть массив положительных и отрицательных чисел. Нужно найти последовательность значений, сумма которой будет наибольшая. Например, для массива [-2, 5, -5, 8, -1, 3, 2, 6] наибольшая сумма будет для последовательности [8, -1, 3, 2, 6].

Решение

Пусть нам дан массив:

src_aray = [x1, x2, x3, x4]

Тогда для решения поставленной задачи нужно вычислить и найти наибольшее для следующих последовательностей:

x1+x2+x3
x2+x3
x1
x2+x3+x4
x2+x3
x2
x3+x4
x3
x4


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

Тогда алгоритм будет такой:
1. Массив проверяется на наличие положительных чисел.
2. Пошагово проверяем каждый элемент массива xi.
3. Если в массиве нет положительных чисел (худший вариант), вычисляем сумму всех последовательностей, начинающихся с xi.
4. Если в массиве есть положительные числа, вычисляем сумму всех последовательностей, начинающихся с xi, только в случае xi > 0.
5. Среди вычисленных сумм, выбираем наибольшую.

Реализовать этот алгоритм можно так:


// допускаем, что данные всегда передаются валидные
// src_array - исходный массив
// len - его длина
// sindex, eindex - результат поиска - начальный и
// конечный индексы последовательности
void sub_array(int *src_array, int len,
int &sindex, int &eindex)
{
int sum = src_array[0];
sindex = 0;
eindex = 0;

// проверяем наличие положительных значений
bool has_positive = false;
for(int i=0;i < len;i++)
if(src_array[i]>0)
{
has_positive = true;
break;
}

for(int i=0;i < len;i++)
{
int ssum = src_array[i];
if(has_positive && ssum < 0) continue;

for(int j=i;j < len;j++)
{
ssum += j>i?src_array[j]:0;
if(ssum>=sum)
{
sum = ssum;
sindex = i;
eindex = j;
}
}
}
}

10 комментариев:

zwitter комментирует...

8-9 класс средней школы...

sash_ko комментирует...

иногда полезно вспомнить, что было в школе :)

sash_ko комментирует...

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

COTOHA комментирует...

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

...
std::vector<int> array;
int maxSum = INT_MIN; // Максимальная сумма
unsigned posStart; // Начальная позиция в массиве, с которой начинается максимальная сумма
unsigned posEnd; // Конечная позиция в массиве, в которой заканчивается максимальная сумма
unsigned curPosEnd; // Конечная позиция в массиве, в которой заканчивается текущая цепочка чисел
...

// Функция считает максимально достижимую сумму, начиная цепочку с элемента pos
int getMaxSum(unsigned pos)
{
int res = 0;

if (pos >= array.size())
return 0; // Сумма для элементов за границами массива равна 0;
if (pos == (array.size() - 1))
{
res = array[pos]; // Сумма для последнего элемента массива будет равна самому элементу
curPosEnd = pos; // Текущий элемент становится хвостом цепочки
}
else
{
res = array[pos];
int rightSum = getMaxSum(pos + 1); // Максимальная сумма для элемента, следующего справа за текущим
if (rightSum > 0) // Есть что взять?
res += rightSum; // Берём
else
curPosEnd = pos; // Иначе нефиг вправо лазить и хватать минусы. Теперь хвост здесь
}

if (res > maxSum) // Побили рекорд?
{
maxSum = res; // Обновляем результаты
posEnd = curPosEnd;
posStart = pos;
}

return res;
}

Ivan A-R комментирует...

>>> 3. Если в массиве нет положительных чисел (худший вариант), вычисляем сумму всех последовательностей, начинающихся с xi.

Вроде достаточно найти максимальное число. Это и будет искомая последовательность (из одного члена). Добавление любого другого члена ухудшит ситуацию =)

sash_ko комментирует...

2Ivan A-R: точно! слона то я и не приметил :) для массива отрицательных чисел просто ищется максимальное

sash_ko комментирует...

2COTOHA: хорошее решение, только не понравилось использование глобальных переменных

Анонимный комментирует...

Вообще эта задача имеет сложность O(n) и существует простейший сканирующий алгоритм, который решаёт её за такое время

legolegs комментирует...

Почитал ваш пост, решил попробовать. Написал, решил оптимизировать. Оптимизация простеньная, но перед её внедрением написал тесты и не зря - нашёл регрессию. Тесты рулят :) Увлёкся, написал всякую обвязку, затем добавил ваше решение (немножко бажное) и вариант СОТОНЫ. О рекурсивном варианте скажу особо: он охрененно быстр. Даже замена глобальных переменных на аргументы по ссылке его не сильно замедлила. Вот что значит правильно выбранный алгоритм. Полученный исходник можно глянуть тут:
http://pastebin.mozilla-russia.org/103786 Есть тесты, нагрузочные тесты (вскрыли проблемы, которые я не учёл в обычных тестах) и бенчмарк.
В ходе реализации получил море удовольствия, спасибо за повод :)

galeyev комментирует...

Действительно интересная задача, нашел полное описание и примеры алгоритмов http://codelab.ru/task/max_sum_sequence/