Задача, немного интересно :)

Это реферальная система?

Я для себя использую вариант на Мускуле с таблицей из 3 полей(`id`, `refer_id`, `referal_id`, `level`)

Пусть она и избыточна(если у юзера есть реферал 5 уровня, то он не ищется перебором рефералов 1,2,3,4 уровней, а пишется в БД).

Даже если записей будет 10 миллионов, то индексы сделают свое дело(в таблице только данные типа int)

Нет, к сожалению не рефералка. По факту мне нужно найти сумму чисел, цепочку, чья сумма значений будет максимальной.

Это вообще что такое? Чем больше инфы - тем лучше, сам знаешь;)

Можно(опять же, я не знаю что это за велосипед и для каких целей нужен) к примеру держать таблицу в мускуле(родительID, ребенокID, сумма от самого старшего родителя).

Потом просто находим max(`summa_ot_samogo_starshego_roditel9`) и уже вычисляем саму цепочку чисел из другой таблицы(id, num) если надо.

При построении этого двоичного дерева храните не только значение отдельного листа, но и сразу вычисляйте сумму значения предка и текущего листа. Тогда конечные листы ("дно пирамиды") будут содержать максимально возможные значения. Для определения цепочки - просто выполнить обратный обход дерева. Т.е. самый выгодный маршрут будет 4-1-20, а не 4-10-2, как может показаться при обходе с корня:

Да это просто задача, что-то типа преддипломной практики, взялся называется, теперь незнаю как решить.

Вариант с расчетом и хранением суммы от родителя - да, рассматриваю. Но по факту у него слабое место - много итераций, вот и думаю как уменьшить, как вывернуться :)

Если бы было к примеру, что на 1 уровне десятки, на 2 сотки, на 3 тысячи и т.д. То есть знать, что в родителе число всегда меньше(или наоборот больше), чем в потомке, тогда да, тупая рекурсивная функция для массива(ищем ключ, который больше/меньше всех своих соседей(они такого же уровня), форычим значение(если массив) этого ключа).

А если числа во всех ячейках рандомные(любая ячейка от 0 до +~), то скорей всего без полного перебора всех комбинаций не обойтись.

ЗЫ. там че в условии задачи написано: "программа должна работать на тетрисе":D

В каком месте много итераций? Вам нужно построить дерево на основе существущих данных, с дополнительными признаками у листа (сумма, "есть дочки") взять максимальное значение со "дна пирамиды" ("нет дочки"), продвинуться к корню дерева и перевернуть полученную цепочку. Задача в-общем, тривиальная.

От полного перебора никак не уйдешь!!!

Ты же заранее не знаешь, где и какие числ. Они же ведь везде рандомные и в 10 потомке может быть число в 100500 раз больше чем в родителе. Поэтому необходимо построить древо.

Если уж без БД, то ситуация очень похожа на рекурсивную функцию для обхода директории(если директория - заходим в нее и опять вызываем функцию, а если файл, то отображаем его название). Тут все также: если значение ячейки == массив - делаем то что надо(суммируем и т.д.), а если число, то значит конец и надо продолжать, пока не будет конец конца:D

Если есть память, то можно дополнительно использовать массив указателей на листья без "дочек", "дно пирамиды". В этом случае полный обход дерева и рекурсии не нужны.

Оптимизайка, а для указателей Вы будете использовать линейный(есть еще условый и циклический) алгоритм? Доступ к ячейки к указателям массива не есть перебор этого самого массива?

Перебор по-любому нужен, хоть с указателями, хоть без! Потому что Вы не можете знать где какое число, и Вам по-любому нужно все просчитать.

ПокАжите решение без рекурсии и без обхода(не получая доступ к ячейкам) массива - либо вырву тот волос(он уже заждался, когда же я проиграю пари), либо отсеку ту(не совсем ту, та была отсечена, не дождавшись когда я проспорю) белую часть ногтя;D