Постановка задачи
Дан массив arr[] из N целых чисел. Найдите смежный подмассив (содержащий хотя бы одно число), который имеет минимальную сумму, и верните его сумму.
ссылку на задачу можно найти здесь, https://practice.geeksforgeeks.org/problems/smallest-sum-contiguous-subarray/1.
Примеры входных и выходных данных
Пример 1
Input:
arr[] = {3,-4, 2,-3,-1, 7,-5}
Output: -6
Explanation:
sub-array which has smallest
sum among all the sub-array is {-4,2,-3,-1} = -6
Пример 2
Input:
arr[] = {2, 6, 8, 1, 4}
Output: 1
Explanation:
sub-array which has smallest
sum among all the sub-array is {1} = 1
Ожидаемая временная сложность: O(N)
Ожидаемое вспомогательное пространство: O(1)
Решение
Наиболее простое и эффективное решение основано на алгоритме Кадана. Который перемещает итератор (здесь упоминается как текущая сумма) от элемента к элементу, при этом после каждого обновления значения итератора, или текущей суммы, это значение сверяется с минимальной суммой результата, если минимальная сумма достигает дальнейшего минимального значения, то содержимое обновляется, иначе нет.
Тем временем, если текущая сумма где-либо превышает 0, то нам необходимо сбросить текущую сумму в ноль. Это означает, что для любого значения здесь и далее имеет смысл игнорировать подмассив до этого момента, так как если его рассматривать, то это приведет к небольшому количеству положительных чисел, что в свою очередь будет противоречить интересам задачи нахождения минимального числа (в которое вносят вклад только отрицательные числа). Поэтому избегайте брать положительные числа в текущую сумму.
class Solution
{
static int smallestSumSubarray(int a[], int size) {
int minSum = Integer.MAX_VALUE;
int curSum = 0;
for(int i : a) {
curSum += i;
minSum = Math.min(minSum, curSum);
curSum = Math.min(curSum, 0);
}
return minSum;
}
}