Ежедневен бит(д) на C++ #168, Често срещан проблем при интервю: Максимална сума на подмасив.
Днес ще разгледаме често срещан проблем за интервю в C++: Максимална сума на подмасив.
При даден непразен масив от цели числа, определете максималната сума на подмасива, т.е. максималната сума от последователни елементи.
Например за входа {-1,1,2,-1,3,-2,1}, максималната сума на подмасива е 5, постигната чрез сумиране подмасива {1,2,-1,3}.
Преди да продължите да четете решението, препоръчвам ви да опитате да го решите сами. Ето връзка към Compiler Explorer с няколко тестови случая: https://compiler-explorer.com/z/bd9d4Pj78.
Решение
Първото наблюдение е, че за да подобрим сбор, искаме да добавим само положителни числа. Има обаче едно усложнение. Отрицателно число може да бъде част от максимална сума, ако има по-големи суми от двете страни, напр. {1,2,-1,3}.
Така че нека помислим кога не искаме да включим отрицателно число в сбора. Ако вървим отляво надясно, това е точно когато сумата отляво е по-висока от абсолютната стойност на този елемент. Например, ако текущата ни ситуация е {1,2,-4}, няма значение какво следва; знаем, че тази част от масива няма да може да допринесе (1+2 все още може да бъде общият максимум).
С това можем да конструираме решение. Отивайки отляво надясно, можем да проследим максималния подмасив, завършващ на тази позиция. Можем да изчислим максималния подмасив, като добавим максималния подмасив за предишната позиция към текущия елемент; но само ако предишният максимум е бил положителен.
#include <vector>
#include <ranges>
int maximum_subarray_sum(const std::vector<int>& nums) {
int sum = nums.front();
int max = nums.front();
for (auto v : nums | std::views::drop(1)) {
sum = std::max(0, sum) + v;
max = std::max(max, sum);
}
return max;
}
