Найти подпоследовательность с наибольшей суммой элементов в массиве
Недавно я взял интервью у компании, и они попросили меня написать алгоритм, который находит подпоследовательность с наибольшей суммой элементов в массиве. Элементы в массиве могут быть отрицательными. Есть ли решение O (n) для этого? Любые хорошие решения очень ценятся.