Цей пост стосується питання, яке я знайшов під час онлайн-оцінювання в BNY. Було одне легке, два середніх і одне важке питання, і це відноситься до середніх питань.
Я не зміг вирішити його тоді, але це питання не виходило з моєї голови. Я не бачив жодних статей чи подібних питань на жодній з платформ для програмування, тому я вирішив опублікувати його тут.
Умова задачі:
Вам дається масив розміру n. Ваше завдання — знайти таку підпослідовність цього масиву, де розмір підмасиву не більше ніж ‘k’, і сума всіх елементів підмасиву є максимальною серед усіх таких підмасивів. Тобто, максимальна сума підмасиву з розміром не більше ніж k.
Приклад вхідних даних:
n k
arr0 arr1 arr2 ...
7 4
-10 1 -9 3 5 -2 7
Приклад вихідних даних:
13
Моя первісна інтуїція:
Моя первісна інтуїція полягала в тому, щоб використовувати звичайний алгоритм Кадена до того моменту, поки розмір підмасиву не досягне ліміту ‘k’. Після цього, щоб додати один елемент, ми б видаляли один з іншого кінця, що виглядало б ось так:
. . . [4 -2 -1 7] 3 . . → . . . 4 [-2 -1 7 3] . .
Звісно, не було б сенсу зберігати від’ємні елементи безпосередньо після видаленого елемента, оскільки вони не сприяють максимізації суми. Але просто видаляти негайно від’ємні елементи було недостатньо, оскільки можуть бути більші від’ємні елементи, які ховаються за позитивними.
Ми повинні знайти та видалити цілу частину підмасиву, сума якого насправді стала від’ємною після видалення елемента:
. . . [10 -1 3 -9 5] 4 . . → . . . 10 -1 [3 -9 5 4] . .
Як ви можете бачити, 3 приховує -9 від видалення.
Тепер моя стратегія полягала в тому, щоб відслідковувати мінімальне значення поточного підмасиву і при видаленні перевіряти, чи стає мінімальне значення непозитивним, віднімаючи видалене значення. Якщо воно стає непозитивним, ми видаляємо всю частину підмасиву зліва від мінімуму разом з самим мінімумом.
Проблема з таким підходом в тому, що це лише говорить нам, що частина до мінімального значення була від’ємною, але не гарантує, що права сторона буде позитивною. Очевидно, ми не можемо шукати точку перегину в підмасиві, оскільки це призведе до рішення з складністю O(N²).
Остаточне рішення:
Розглянемо наступний графік:
Цей графік представляє масив префіксних сум, де графік піднімається, коли масив містить позитивні значення, і опускається, коли він містить від’ємні значення.
Тепер, якщо ми подивимося на графік з вікна розміру k і виділимо максимуми графіка:
Як видно, A — це найвища точка префіксної суми для перших k значень. Тому буде правильним припустити, що для перших k елементів максимальна сума підмасиву буде між точкою O та точкою A. Отже, все, що нам потрібно зробити — це порівняти суму від O до A з глобальним максимумом. Але є нюанс: лінія між O та A може виглядати ось так:
У цьому випадку максимальний підмасив суми буде між x та A.
Це означає, що нам слід перевірити суму підмасиву, утвореного кожним елементом від O до A з A. Це дасть нам найкращу суму між O та A. Але, оскільки ми рухаємось від точки O до O+1, наше вікно пошуку зменшується з k до k-1. Тому ми також повинні пересунути наше вікно на один крок вперед з k до k+1.
Перше ітерація: (вікно: від O до K, сума підмасиву: від O до A)
Друге ітерація: (вікно від O+1 до K+1,
сума підмасиву: від O+1 до A)
Коли ми це робимо, ми також повинні оновлювати список максимумів, з якими ми взаємодіємо з більшими елементами масиву. Якщо з’являється, скажімо, інший елемент C з префіксної суми, який більший за A, то замість перевірки суми від O+1 до A ми перевіримо від O+1 до C.
Також, якщо ми закінчили перевірку всіх значень у діапазоні, як від O до C, то ми повинні продовжити перевірку від C до наступного максимуму. Ось чому ми повинні відслідковувати максимуми.
Це призводить до рішення з часовою складністю близько O(N). Оскільки нам потрібно відслідковувати наступні максимуми в масиві, що має деякі додаткові накладні витрати (я використав мономіальний стек), але я не турбувався про точний розрахунок часової складності для цього.
Я публікую свою реалізацію тут, зверніть увагу, що можуть бути деякі поліпшення в коді, але я не маю енергії для їх впровадження, тому прийміть це так, як є.
int modifiedKaiden(int arr[],int n, int k)
{
vi stackMax={n}; // Для відслідковування максимальних значень.
// Я заповнив його n, щоб мати початкове значення для порівняння, знаю, що це дурість.
vi prefixSum(n+1);
prefixSum[n]=0; // Встановлюємо в 0, тому що я використовував n як початкове значення.
int start=0;int end=k-1;
int val=0;
rep(i,0,k) // Проходимо через початкове вікно з k і обчислюємо префіксні суми та максимуми.
{
val+=arr[i]; // Обчислюємо префіксну суму.
prefixSum[i]=val;
while(stackMax.size() && val>prefixSum[stackMax[stackMax.size()-1]]) // Запихаємо більші максимуми глибше в стек.
{
stackMax.pop_back();
}
stackMax.push_back(i);
}
int mx=0; // глобальний максимум
int stackStart=0; // Я назвав це стеком, але я використовую глибші значення в стеці.
while(startstackStart && val>prefixSum[stackMax[stackMax.size()-1]])
{
stackMax.pop_back();
}
stackMax.push_back(end);
}
}
return mx;
}
Перекладено з: [Maximum sum subarray with size less than or equal to k](https://medium.com/@sg550js/maximum-sum-subarray-with-size-less-than-or-equal-to-k-ac270d3ad903)