Разделяй и властвуй

Подход «разделяй и властвуй» — это способ рекурсивного решения проблем путем применения трех шагов.

Разделите проблему на несколько подзадач, которые являются более мелкими экземплярами одной и той же проблемы.

преодолейте подзадачи, рекурсивно рекурсивно, и если размер подзадачи достаточно мал (базовый случай), просто решите ее прямолинейно.

Объединить решения подзадачи в решение исходной проблемы

когда подзадачи достаточно велики, мы называем этот случай рекурсивным, а когда подзадачи становятся достаточно маленькими или тривиальными для решения, мы называем этот базовый случай

рецидивы

повторение - это уравнение, описывающее функцию с точки зрения ее значения при меньшем вводе, например, время выполнения сортировки слиянием.

T(n) = 2T(n/2) + O(n)

Основной метод обеспечивает границы для повторений формы

T(n) = a T(n/b) + f(n)

где a ≥1, b › 1 и f (n) — заданная функция. Такие рецидивы возникают
часто. Повторение формы уравнение характеризует алгоритм "разделяй и властвуй", который создает подзадачи, каждая из которых составляет 1/b размера исходной задачи, и в которых этапы "разделяй и объединяй" занимают вместе ф (н) время

проблема максимального подмассива

Ввод при условии, что у нас есть массив длины N

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

решение с использованием разделяй и властвуй

подход «разделяй и властвуй» предполагает, что мы разделяем проблему на более мелкие подзадачи, поэтому нам нужно разделить массив [low..high] на два равных подмассива, которые нам нужны, чтобы найти среднюю точку

теперь у нас есть два массива A[low….mid] и A[mid….high], поэтому максимальный подмассив должен лежать в одном из следующих мест

  • максимальный подмассив целиком лежит в первой половине A[low…mid] low
  • максимальный подмассив целиком лежит во второй половине A[mid….high]
  • максимальный подмассив пересекает среднюю точку

максимальный подмассив A[low… high] должен лежать в одном из этих мест, и он должен иметь наибольшую сумму по всем подмассивам в A[low..mid] и A[mid…high] и пересекать среднюю точку

поэтому поиск максимального подмассива A[low…mid] и A[mid…high] — это та же проблема с вводом меньшего размера, поэтому мы можем получить их рекурсивно

поэтому все, что нам нужно сделать, это получить максимальный подмассив, который пересекает среднюю точку

ограничение, что подмассив должен пересекать среднюю точку, дает нам очень важную информацию о том, что максимальный подмассив, пересекающий среднюю точку, состоит из двух подмассивов A[i….mid] и A[mid+1…j], поэтому мы нужно найти их и объединить

#include<iostream>
#include<vector>
using namespace std;
int FindCrossingMidpointSubArray(vector<int>arr,int low,int mid,int high){
    int leftSum = 0;
    int leftMax=INT32_MIN;
    int leftIDx=0;
    for(int i = mid-1 ;i>=low;i--){
        leftSum+=arr[i];
        if(leftSum>leftMax){
            leftIDx = i;
            leftMax = leftSum;
        }
    }

    int rightSum = 0;
    int rightMax=INT32_MIN;
    int rightIDx=0;
    for(int i = mid ;i<high;i++){
        rightSum+=arr[i];
        if(rightSum>rightMax){
            rightIDx = i;
            rightMax = rightSum;
        }
    }
    return leftMax+rightMax;
}
int maxSubArray(vector<int>& nums) {
    if(nums.size()==1){
        return nums[0];
    }
    int mid = nums.size()/2;
    vector<int> left(nums.begin(),nums.begin()+mid);
    vector<int> right(nums.begin()+mid,nums.end());
    int leftMax = maxSubArray(left);
    int rightMax = maxSubArray(right);
    int crossingMax = FindCrossingMidpointSubArray(nums,0,mid,nums.size());
    cout<<leftMax<<" "<<rightMax<<" "<<crossingMax<<" "<<endl;
    return max(leftMax,max(rightMax,crossingMax));
}

int main(){
    vector<int> test{-2,-1};
    int max = maxSubArray(test);
    cout<<max<<endl;
}

анализ алгоритма разделяй и властвуй

нам нужно настроить повторение, которое описывает время выполнения рекурсивной процедуры maxSubArray T (n) будет обозначать время выполнения алгоритма

рекурсивный случай возникает, когда n>1 каждый рекурсивный вызов работает с n/2 элементами, поэтому мы тратим T(n/2) времени на их решение

обратите внимание, что процедура FindcrossingSubArray выполняется во время лайнера

so T(n) = 2T(n/2) + Θ(n)

а как решить такой рецидив

основной метод решения рецидивов

мастер-метод решает повторения формы

T(n) = A*(n/B) + f(N)

рекуррентность описывает время выполнения алгоритма, который делит задачу размера N на A подзадач, каждая из которых имеет размер n/b, где A и B — положительные константы, а f(N) включает в себя затраты на разделение задачи и объединение результата подзадач

теорема

пусть a ≥ 1 и b ≥ 1 — константы, пусть f(n) — функция, а T(n) определяется на целых неотрицательных числах рекуррентным выражением

для задачи максимального подмассива

a = 2 и b = 2 и f (n) = O (n)

который попадает в случай 2, поэтому время выполнения задачи о максимальном подмассиве составляет O (nlogn)