Пошук підмасиву з максимальною/мінімальною сумою

Тут ми розглядаємо задачу пошуку підмасиву з максимальною сумою, а також деякі її варіації (зокрема алгоритм для онлайн-розв'язання цієї задачі).

Постановка задачі

Дано масив чисел $a[1 \ldots n]$. Потрібно знайти підмасив $a[l \ldots r]$ з максимальною сумою:

$$\max_{ 1 \le l \le r \le n } \sum_{i=l}^{r} a[i].$$

Наприклад, якщо всі цілі числа в масиві $a[]$ невід'ємні, то відповіддю буде сам масив. Однак розв'язок стає нетривіальним, коли масив може містити як додатні, так і від'ємні числа.

Зрозуміло, що задача пошуку мінімального підмасиву по суті така сама — потрібно лише змінити знаки всіх чисел.

Коли підходить цей алгоритм?

• Чи шукаємо неперервний підмасив (відрізок), а не довільну підмножину елементів?
• Чи цільова функція — сума елементів (можливо, з додатними та від'ємними значеннями)?
• Чи потрібно вкластися в один прохід $O(n)$ замість перебору всіх $O(n^2)$ відрізків? (для пошуку максимального середнього з обмеженням на довжину — поєднай із бінарним пошуком)

Алгоритм 1

Тут ми розглянемо майже очевидний алгоритм. (Далі ми розглянемо інший алгоритм, який трохи важче придумати, але його реалізація ще коротша.)

Опис алгоритму

Алгоритм дуже простий.

Введемо для зручності позначення: $s[i] = \sum_{j=1}^{i} a[j]$. Тобто масив $s[i]$ — це масив часткових сум масиву $a[]$. Також покладемо $s[0] = 0$.

Тепер ітеруватимемо по індексу $r = 1 \ldots n$ і навчимося швидко знаходити оптимальне $l$ для кожного поточного значення $r$, при якому досягається максимальна сума на підмасиві $[l, r]$.

Формально це означає, що для поточного $r$ нам потрібно знайти таке $l$ (не більше за $r$), щоб значення $s[r] - s[l-1]$ було максимальним. Після тривіального перетворення можна побачити, що нам потрібно знайти в масиві $s[]$ мінімум на відрізку $[0, r-1]$.

Звідси одразу отримуємо розв'язок: ми просто зберігаємо, де знаходиться поточний мінімум у масиві $s[]$. Використовуючи цей мінімум, ми знаходимо поточний оптимальний індекс $l$ за $O(1)$, а при переході від поточного індексу $r$ до наступного просто оновлюємо цей мінімум.

Очевидно, цей алгоритм працює за $O(n)$ і є асимптотично оптимальним.

Реалізація

Щоб його реалізувати, нам навіть не потрібно явно зберігати масив часткових сум $s[]$ — нам знадобиться лише поточний елемент із нього.

Реалізація наведена для масивів з 0-індексацією, а не для 1-нумерації, як описано вище.

Спершу наведемо розв'язок, який знаходить просту числову відповідь, не знаходячи індексів шуканого відрізка:

C++

int ans = a[0], sum = 0, min_sum = 0;

for (int r = 0; r < n; ++r) {
    sum += a[r];
    ans = max(ans, sum - min_sum);
    min_sum = min(min_sum, sum);
}

Python

ans, total, min_sum = a[0], 0, 0

for r in range(n):
    total += a[r]
    # найкращий відрізок із кінцем у r: поточна сума мінус мінімальний префікс
    ans = max(ans, total - min_sum)
    min_sum = min(min_sum, total)

TypeScript

let ans = a[0], sum = 0, minSum = 0;

for (let r = 0; r < n; ++r) {
    sum += a[r];
    // найкращий відрізок із кінцем у r: поточна сума мінус мінімальний префікс
    ans = Math.max(ans, sum - minSum);
    minSum = Math.min(minSum, sum);
}

Go

ans, sum, minSum := a[0], 0, 0

for r := 0; r < n; r++ {
    sum += a[r]
    // найкращий відрізок із кінцем у r: поточна сума мінус мінімальний префікс
    ans = max(ans, sum-minSum)
    minSum = min(minSum, sum)
}

Тепер наведемо повну версію розв'язку, яка додатково знаходить також межі шуканого відрізка:

C++

int ans = a[0], ans_l = 0, ans_r = 0;
int sum = 0, min_sum = 0, min_pos = -1;

for (int r = 0; r < n; ++r) {
    sum += a[r];
    int cur = sum - min_sum;
    if (cur > ans) {
        ans = cur;
        ans_l = min_pos + 1;
        ans_r = r;
    }
    if (sum < min_sum) {
        min_sum = sum;
        min_pos = r;
    }
}

Python

ans, ans_l, ans_r = a[0], 0, 0
total, min_sum, min_pos = 0, 0, -1

for r in range(n):
    total += a[r]
    cur = total - min_sum
    if cur > ans:
        ans = cur
        ans_l = min_pos + 1  # відрізок починається одразу після мінімуму
        ans_r = r
    if total < min_sum:
        min_sum = total
        min_pos = r

TypeScript

let ans = a[0], ansL = 0, ansR = 0;
let sum = 0, minSum = 0, minPos = -1;

for (let r = 0; r < n; ++r) {
    sum += a[r];
    const cur = sum - minSum;
    if (cur > ans) {
        ans = cur;
        ansL = minPos + 1; // відрізок починається одразу після мінімуму
        ansR = r;
    }
    if (sum < minSum) {
        minSum = sum;
        minPos = r;
    }
}

Go

ans, ansL, ansR := a[0], 0, 0
sum, minSum, minPos := 0, 0, -1

for r := 0; r < n; r++ {
    sum += a[r]
    cur := sum - minSum
    if cur > ans {
        ans = cur
        ansL = minPos + 1 // відрізок починається одразу після мінімуму
        ansR = r
    }
    if sum < minSum {
        minSum = sum
        minPos = r
    }
}

Алгоритм 2

Тут ми розглянемо інший алгоритм. Його трохи важче зрозуміти, але він елегантніший за наведений вище, а його реалізація трохи коротша. Цей алгоритм запропонував Jay Kadane у 1984 році.

Опис алгоритму

Сам алгоритм такий. Пройдемося масивом і накопичуватимемо поточну часткову суму в деякій змінній $s$. Якщо в якийсь момент $s$ стає від'ємним, ми просто присвоюємо $s=0$. Стверджується, що максимум серед усіх значень, яких змінна $s$ набуває протягом роботи алгоритму, і буде відповіддю до задачі.

Доведення:

Розглянемо перший індекс, коли сума $s$ стає від'ємною. Це означає, що, починаючи з нульової часткової суми, ми зрештою отримуємо від'ємну часткову суму — отже, весь цей префікс масиву, як і будь-який його суфікс, має від'ємну суму. Тому цей підмасив ніколи не дає внеску в часткову суму жодного підмасиву, префіксом якого він є, і його можна просто відкинути.

Однак цього недостатньо, щоб довести коректність алгоритму. В алгоритмі ми фактично обмежені в пошуку відповіді лише такими відрізками, які починаються одразу після місць, де ставалося $s<0$.

Але насправді розглянемо довільний відрізок $[l, r]$, причому $l$ не знаходиться в такій «критичній» позиції (тобто $l > p+1$, де $p$ — остання така позиція, в якій $s<0$). Оскільки остання критична позиція знаходиться строго раніше за $l-1$, виходить, що сума $a[p+1 \ldots l-1]$ невід'ємна. Це означає, що, перемістивши $l$ у позицію $p+1$, ми збільшимо відповідь або, у крайньому випадку, не змінимо її.

Так чи інакше, виходить, що при пошуку відповіді можна обмежитися лише відрізками, які починаються одразу після позицій, у яких з'явилося $s<0$. Це доводить коректність алгоритму.

Реалізація

Як і в алгоритмі 1, спершу наведемо спрощену реалізацію, яка шукає лише числову відповідь без знаходження меж шуканого відрізка:

C++

int ans = a[0], sum = 0;

for (int r = 0; r < n; ++r) {
    sum += a[r];
    ans = max(ans, sum);
    sum = max(sum, 0);
}

Python

ans, total = a[0], 0

for r in range(n):
    total += a[r]
    ans = max(ans, total)
    total = max(total, 0)  # якщо сума стала від'ємною — починаємо заново

TypeScript

let ans = a[0], sum = 0;

for (let r = 0; r < n; ++r) {
    sum += a[r];
    ans = Math.max(ans, sum);
    sum = Math.max(sum, 0); // якщо сума стала від'ємною — починаємо заново
}

Go

ans, sum := a[0], 0

for r := 0; r < n; r++ {
    sum += a[r]
    ans = max(ans, sum)
    sum = max(sum, 0) // якщо сума стала від'ємною — починаємо заново
}

Повний розв'язок, який підтримує індекси меж відповідного відрізка:

C++

int ans = a[0], ans_l = 0, ans_r = 0;
int sum = 0, minus_pos = -1;

for (int r = 0; r < n; ++r) {
    sum += a[r];
    if (sum > ans) {
        ans = sum;
        ans_l = minus_pos + 1;
        ans_r = r;
    }
    if (sum < 0) {
        sum = 0;
        minus_pos = r;
    }
}

Python

ans, ans_l, ans_r = a[0], 0, 0
total, minus_pos = 0, -1

for r in range(n):
    total += a[r]
    if total > ans:
        ans = total
        ans_l = minus_pos + 1  # відрізок починається після останнього "обнулення"
        ans_r = r
    if total < 0:
        total = 0
        minus_pos = r

TypeScript

let ans = a[0], ansL = 0, ansR = 0;
let sum = 0, minusPos = -1;

for (let r = 0; r < n; ++r) {
    sum += a[r];
    if (sum > ans) {
        ans = sum;
        ansL = minusPos + 1; // відрізок починається після останнього "обнулення"
        ansR = r;
    }
    if (sum < 0) {
        sum = 0;
        minusPos = r;
    }
}

Go

ans, ansL, ansR := a[0], 0, 0
sum, minusPos := 0, -1

for r := 0; r < n; r++ {
    sum += a[r]
    if sum > ans {
        ans = sum
        ansL = minusPos + 1 // відрізок починається після останнього "обнулення"
        ansR = r
    }
    if sum < 0 {
        sum = 0
        minusPos = r
    }
}

Пов'язані задачі

Пошук максимального/мінімального підмасиву з обмеженнями

Якщо умова задачі накладає додаткові обмеження на шуканий відрізок $[l, r]$ (наприклад, що довжина $r-l+1$ відрізка має бути в заданих межах), то описаний алгоритм, найімовірніше, легко узагальнюється на ці випадки — так чи інакше, задача все одно зводитиметься до пошуку мінімуму в масиві $s[]$ із заданими додатковими обмеженнями.

Двовимірний випадок задачі: пошук максимальної/мінімальної підматриці

Описана в цій статті задача природно узагальнюється на більші розмірності. Наприклад, у двовимірному випадку вона перетворюється на пошук такої підматриці $[l_1 \ldots r_1, l_2 \ldots r_2]$ заданої матриці, яка має максимальну суму чисел у ній.

Використовуючи розв'язок для одновимірного випадку, легко отримати розв'язок за $O(n^3)$ для двовимірного випадку: ми перебираємо всі можливі значення $l_1$ і $r_1$ та обчислюємо суми від $l_1$ до $r_1$ у кожному рядку матриці. Тепер у нас є одновимірна задача пошуку індексів $l_2$ і $r_2$ у цьому масиві, яку вже можна розв'язати за лінійний час.

Швидші алгоритми для розв'язання цієї задачі відомі, але вони не набагато швидші за $O(n^3)$ і дуже складні (настільки складні, що багато з них поступаються тривіальному алгоритму для всіх розумних обмежень за рахунок прихованої константи). Наразі найкращий відомий алгоритм працює за час $O\left(n^3 \frac{ \log^3 \log n }{ \log^2 n} \right)$ (T. Chan 2007 "More algorithms for all-pairs shortest paths in weighted graphs")

Цей алгоритм Chan, як і багато інших результатів у цій галузі, фактично описує швидке множення матриць (де під множенням матриць мається на увазі видозмінене множення: замість додавання використовується мінімум, а замість множення — додавання). Задачу пошуку підматриці з найбільшою сумою можна звести до задачі пошуку найкоротших шляхів між усіма парами вершин, а ця задача, своєю чергою, зводиться до такого множення матриць.

Пошук підмасиву з максимальним/мінімальним середнім

Ця задача полягає в пошуку такого відрізка $a[l, r]$, щоб середнє значення було максимальним:

$$\max_{l \le r} \frac{ 1 }{ r-l+1 } \sum_{i=l}^{r} a[i].$$

Звісно, якщо на шуканий відрізок $[l, r]$ не накладено жодних інших умов, то розв'язком завжди буде відрізок довжини $1$ на максимальному елементі масиву. Задача має сенс лише за наявності додаткових обмежень (наприклад, якщо довжина шуканого відрізка обмежена знизу).

У цьому випадку ми застосовуємо стандартний прийом при роботі із задачами на середнє значення: ми шукатимемо шукане максимальне середнє значення за допомогою бінарного пошуку.

Для цього нам потрібно навчитися розв'язувати таку підзадачу: дано число $x$, і нам потрібно перевірити, чи існує підмасив масиву $a[]$ (звісно, який задовольняє всі додаткові обмеження задачі), де середнє значення більше за $x$.

Щоб розв'язати цю підзадачу, віднімемо $x$ від кожного елемента масиву $a[]$. Тоді наша підзадача фактично перетворюється на таку: чи є в цьому масиві підмасиви з додатною сумою. А цю задачу ми вже вміємо розв'язувати.

Таким чином, ми отримали розв'язок з асимптотикою $O(T(n) \log W)$, де $W$ — потрібна точність, а $T(n)$ — час розв'язання підзадачі для масиву довжини $n$ (який може змінюватися залежно від конкретних додаткових обмежень).

Розв'язання онлайн-задачі

Умова задачі така: дано масив із $n$ чисел і число $L$. Надходять запити вигляду $(l,r)$, і у відповідь на кожен запит потрібно знайти підмасив відрізка $[l, r]$ довжиною не менше за $L$ з максимально можливим середнім арифметичним.

Алгоритм розв'язання цієї задачі досить складний; його запропонував KADR (Ярослав Твердохліб).