Каков алгоритм, чтобы найти максимальную сумму подпоследовательности массива?

Question

Существует одномерный массив с элементами {5,30,99,60,5,10}.Из этого массива 1 подпоследовательность равна 5, 99 и 10, что суммирует до значения 114. Сумма других подпоследовательностей меньше 114. Два элемента не должны быть смежными в подпоследовательности, т. Е. {5, 30 и60} не является допустимой подпоследовательностью (для этой проблемы).Это может быть {5, 99, 5} или {30, 60, 10} и т. Д. Массив не содержит отрицательных чисел.Какой подход будет правильным способом для расчета этой максимальной суммы?Я пытаюсь реализовать это в C.

Answer 1

Рекурсия твой друг здесь

Максимальная сумма

5 + maxSum of {99, 60, 5, 10}

или сбросить 5 в пользу 30 и

30 + maxSum of {60, 5, 10}

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