Найдите самую большую сумму непрерывной последовательности из массива целых чисел, как положительных, так и отрицательных

Это довольно сложная, но очень популярная задача. Давайте решим ее на примере массива:

2 3 -8 -1 2 4 -2 3

Если рассматривать массив как содержащий чередующиеся последовательности положительных и отрицательных чисел, то не имеет смысла рассматривать части положительных или отрицательных субпоследовательностей. Почему? Включая часть отрицательной субпоследовательности, мы уменьшаем итоговое значение суммы, значит, нам не стоит включать часть отрицательной субпоследовательности вообще. Включение части положительной субпоследовательности выглядит еще более странным, поскольку включение этой субпоследовательности целиком всегда даст больший результат.

Нужно придумать алгоритм, рассматривая массив как последовательность отрицательных и положительных чисел, расположенных вперемежку.

Любое число можно представить в виде суммы субпоследовательностей положительных и отрицательных чисел. В нашем примере массив можно сократить до:

5 -9 6 -2 3

Мы еще не получили отличный алгоритм, но теперь лучше понимаем, с чем имеем дело.

Рассмотрим предыдущий массив. Нужно ли учитывать субпоследовательность {5, -9}? В сумме мы получим -4, значит, нет смысла учитывать оба этих числа, достаточно только {5}.

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

Давайте продвигаться, начиная с первого элемента в массиве.

5 — это самая большая сумма, встретившаяся нам. Таким образом, maxsum = 5 и sum = 5. Затем мы видим следующее число (-9). Если добавить это число к sum, то получится отрицательная величина. Нет смысла расширять субпоследовательность с 5 до -9 (-9 уменьшает общую сумму до 4). Таким образом, мы просто сбрасываем значение sum.

Теперь мы дошли до следующего элемента (6). Эта субпоследовательность больше, чем 5, таким образом, мы обновляем значения maxsum и sum.

Затем мы смотрим на следующий элемент (-2). Добавление этого числа к 6 сделает sum = 4. Так как это не окончательное значение, наша субпослсдовательность выглядит как {6, -2}. Мы обновляем sum, но не maxsum.

Наконец мы смотрим па следующий элемент (3). Добавление 3 к sum (4) даст нам 7, таким образом, мы обновляем maxsum. Максимальная последовательность имеет вид {6, -2, 3}.

Когда мы работаем с развернутым массивом, логика остается такой же. Следующий код реализует этот алгоритм:

			public static int getMaxSum(int[] a) {
	int maxsum = 0;
	int sum = 0;
	for (int i = 0; i < a.lenght; i++) {
		sum += a[i];
		if (maxsum < sum) {
			maxsum = sum;
		}	else if (sum < 0) {
				sum = 0;
		}
	}
	return maxsum;
}
		

А если массив состоит из отрицательных чисел? Как действовать в этом случае? Рассмотрим простой массив {-3, -10, -5}. Можно дать три разных ответа:

• -3 (если считать, что субпоследовательность не может быть пустой);
• 0 (субпоследовательность может иметь нулевую длину);
• MINIMUM_INT (для случая ошибки).

В нашем коде был использован второй ответ (sum = 0), но в этом вопросе не существует однозначного «правильного» решения. Обсудите это с интервьюером.

Разбор задачи по книге «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию»