1. Общ преглед
Проблемът с максималния подмасив е задача за намиране на поредицата съседни елементи с максималната сума във всеки даден масив.
Например, в долния масив, маркираният подмасив има максималната сума (6):
В този урок ще разгледаме две решения за намиране на максималния подмасив в масив . Единият от които ще проектираме с O (n) времева и космическа сложност.
2. Алгоритъм на грубата сила
Грубата сила е итеративен подход за решаване на проблем. В повечето случаи решението изисква редица повторения в структурата на данните. В следващите няколко раздела ще приложим този подход за решаване на проблема с максималния подмасив.
2.1. Приближаване
Най-общо казано, първото решение, което ви идва на ум, е да се изчисли сумата на всеки възможен подмраг и да се върне този с максималната сума.
Като начало ще изчислим сумата на всеки подмасив, който започва с индекс 0. По същия начин ще намерим всички подмасиви, започващи при всеки индекс от 0 до n-1, където n е дължината на масива:
Така че ще започнем от индекс 0 и ще добавим всеки елемент към текущата сума в итерацията. Ще следим и максималната сума, видяна до момента . Тази итерация е показана в лявата част на изображението по-горе.
От дясната страна на изображението можем да видим итерацията, която започва с индекс 3 . В последната част на това изображение имаме подмасива с максималната сума между индекси 3 и 6 .
Въпреки това, нашият алгоритъм ще продължи да намерите всички субредове започващи от индексите между 0 и N-1 .
2.2. Изпълнение
Нека сега видим как можем да приложим това решение в Java:
public int maxSubArray(int[] nums) { int n = nums.length; int maximumSubArraySum = Integer.MIN_VALUE; int start = 0; int end = 0; for (int left = 0; left < n; left++) { int runningWindowSum = 0; for (int right = left; right maximumSubArraySum) { maximumSubArraySum = runningWindowSum; start = left; end = right; } } } logger.info("Found Maximum Subarray between {} and {}", start, end); return maximumSubArraySum; }Както се очаква, актуализираме maximumSubArraySum, ако текущата сума е повече от предишната максимална сума. По-специално, ние също така актуализираме началото и края, за да разберем местоположенията на индекса на този подмасив .
2.3. Сложност
Най-общо казано, решението за груба сила се повтаря многократно върху масива, за да се получи всяко възможно решение. Това означава, че времето, необходимо на това решение, нараства квадратично с броя на елементите в масива. Това може да не е проблем за масиви с малък размер. Но тъй като размерът на масива нараства, това решение не е ефективно.
Чрез проверка на кода можем също да видим, че има две вложени за цикли. Следователно можем да заключим, че времевата сложност на този алгоритъм е O (n2) .
В следващите раздели ще разрешим този проблем с O (n) сложност, използвайки динамично програмиране.
3. Динамично програмиране
Динамичното програмиране решава проблем, като го разделя на по-малки подпроблеми. Това е много подобно на техниката за решаване на алгоритъма „разделяй и владей“. Основната разлика обаче е, че динамичното програмиране решава подпроблема само веднъж.
След това съхранява резултата от тази подпроблема и по-късно използва повторно този резултат за решаване на други свързани подпроблеми. Този процес е известен като запомняне .
3.1. Алгоритъм на Кадане
Алгоритъмът на Kadane е популярно решение на проблема с максималния подмасив и това решение се основава на динамично програмиране.
Най-важното предизвикателство при решаването на проблем с динамичното програмиране е намирането на оптималните подпроблеми .
3.2. Приближаване
Нека разберем този проблем по различен начин:
В изображението по-горе приемаме, че максималният подмасив завършва на последното местоположение на индекса. Следователно максималната сума на подмасива ще бъде:
maximumSubArraySum = max_so_far + arr[n-1]max_so_far е максималната сума на подмасив, който завършва с индекс n-2 . Това е показано и на изображението по-горе.
Сега можем да приложим това предположение към всеки индекс в масива. Например, максималната сума на подменъла, която завършва на n-2, може да бъде изчислена като:
maximumSubArraySum[n-2] = max_so_far[n-3] + arr[n-2]Следователно можем да заключим, че:
maximumSubArraySum[i] = maximumSubArraySum[i-1] + arr[i]Тъй като всеки елемент в масива е специален подмасив с размер един, ние също трябва да проверим дали елемент е по-голям от самата максимална сума:
maximumSubArraySum[i] = Max(arr[i], maximumSubArraySum[i-1] + arr[i])Разглеждайки тези уравнения, можем да видим, че трябва да намерим максималната сума на подмасива при всеки индекс на масива. По този начин ние разделихме нашия проблем на n подпроблеми. Можем да намерим максималната сума при всеки индекс, като повторим масива само веднъж:
Маркираният елемент показва текущия елемент в итерацията. При всеки индекс ще приложим уравнението, получено по-рано, за да изчислим стойност за max_ending_here . Това ни помага да определим дали трябва да включим текущия елемент в подмасива или да стартираме нов подмасив, започвайки от този индекс .
Another variable, max_so_far is used to store the maximum subarray sum found during the iteration. Once we iterate over the last index, max_so_far will store the sum of the maximum subarray.
3.3. Implementation
Again, let's see how we can now implement the Kadane algorithm in Java, following the above approach:
public int maxSubArraySum(int[] arr) { int size = arr.length; int start = 0; int end = 0; int maxSoFar = 0, maxEndingHere = 0; for (int i = 0; i maxEndingHere + arr[i]) { start = i; maxEndingHere = arr[i]; } else maxEndingHere = maxEndingHere + arr[i]; if (maxSoFar < maxEndingHere) { maxSoFar = maxEndingHere; end = i; } } logger.info("Found Maximum Subarray between {} and {}", start, end); return maxSoFar; }Here, we updated the start and end to find the maximum subarray indices.
3.4. Complexity
Since we only need to iterate the array once, the time complexity of this algorithm is O(n).
So as we can see, the time taken by this solution grows linearly with the number of elements in the array. Consequently, it is more efficient than the brute force approach we discussed in the last section.
4. Conclusion
В този бърз урок описахме два начина за решаване на проблема с максималния подмасив.
Първо, изследвахме подход на груба сила и видяхме, че това итеративно решение доведе до квадратично време. По-късно обсъдихме алгоритъма на Kadane и използвахме динамично програмиране за решаване на проблема в линейно време.
Както винаги, пълният изходен код на статията е достъпен в GitHub.