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

1. Подход грубой силы:

   • Сгенерировать все возможные подмассивы данного массива.
   • Вычислить сумму каждого подмассива.
   • Отслеживать максимальную сумму.
   • Вернуть максимальную сумму.

2. Алгоритм Кадане:

   • Инициализируйте две переменные: maxSum и currentSum, обеим присваивается первый элемент массива.
   • Пройтись по массиву, начиная со второго элемента.
   • Для каждого элемента обновите currentSum, добавив текущий элемент или создав новый подмассив.
   • Обновить maxSum, если currentSum больше.
   • Вернуть maxSum.

3. Динамическое программирование:

   • Создайте вспомогательный массив dp того же размера, что и входной массив.
   • Инициализировать dp[0] как первый элемент массива.
   • Перебрать оставшиеся элементы массива.
   • Для каждого элемента обновите dp[i] как максимальное значение dp[i-1] + array[i] и array[i].
   • Вернуть максимальное значение в массиве dp.

4. Разделяй и властвуй:

   • Разделите массив на две половины.
   • Рекурсивно найти максимальную сумму подпоследовательности в левой половине, правой половине и подмассиве, пересекающем среднюю точку.
   • Вернуть максимальную из трёх сумм.