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

Для того чтобы найти подпоследовательность непрерывных чисел с максимальной суммой, можно использовать алгоритм "максимальной суммы подпоследовательности" (Kadane's algorithm).

Этот алгоритм основывается на идее, что максимальная сумма подпоследовательности будет либо суммой элементов от начала до конца (если она положительна), либо нулем (если все элементы последовательности отрицательные).

Итак, предположим, у нас есть массив nums, в котором хранятся числа, и нам необходимо найти подпоследовательность непрерывных чисел с максимальной суммой.

Сначала создадим две переменные: maxSum и currentSum. Переменная maxSum будет содержать максимальную сумму подпоследовательности, а currentSum - текущую сумму подпоследовательности.

Затем пройдемся по массиву nums в цикле. На каждой итерации будем обновлять текущую сумму подпоследовательности следующим образом:
1. Если currentSum + текущий элемент больше текущего элемента, то мы продолжаем текущую подпоследовательность;
2. Если текущий элемент больше суммы текущей последовательности, то мы начинаем новую последовательность с текущего элемента.

Далее сравниваем currentSum с maxSum и обновляем maxSum, если необходимо.

В конце цикла в переменной maxSum будет содержаться максимальная сумма подпоследовательности.

Вот пример кода на языке Java:

public int maxSubarraySum(int[] nums) {
    int maxSum = nums[0];
    int currentSum = nums[0];
    
    for (int i = 1; i < nums.length; i++) {
        currentSum = Math.max(nums[i], currentSum + nums[i]);
        maxSum = Math.max(maxSum, currentSum);
    }
    
    return maxSum;
}

Пример использования данной функции:

int[] nums = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
int maxSum = maxSubarraySum(nums);
System.out.println(maxSum); // Выводит 6 (сумма подпоследовательности [4, -1, 2, 1])

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