Comment résoudre "sous-réseau maximum de taille fixe" en utilisant la méthode de division et de conquête?

Question

Avertissement: Je sais que ce problème peut être résolu avec un seul passage de tableau très efficacement, mais je suis intéressé à le faire avec diviser pour régner parce que c'est un peu différent des problèmes typiques que nous abordons avec diviser pour régner. Supposons que vous receviez un tableau à virgule flottante X [1: n] de taille n et de longueur d'intervalle l. Le problème est de concevoir un algorithme de division et de conquête pour trouver le sous-tableau de longueur l à partir du tableau qui a la somme maximale.

Voici ce que j'ai trouvé. Pour un tableau de longueur n, il y a n-l + 1 sous-tableaux de l éléments consécutifs. Par exemple pour un tableau de longueur n = 10 et l = 3, il y aura 8 sous-tableaux de longueur 3.

Maintenant, pour diviser le problème en deux, j'ai décidé de rompre le tableau à n-l + 1/2 de sorte qu'un nombre égal de sous-réseaux soit distribué aux deux moitiés de ma division comme indiqué dans l'algorithme ci-dessous. Encore une fois, pour n = 10, l = 3, n-l + 1 = 8, donc j'ai divisé le problème en (n-l + 1)/2 = 4. Mais pour le 4ème sous-tableau j'ai besoin d'éléments de 6 ie (n + l-1)/2.

void FixedLengthMS(input: X[1:n], l, output: k, max_sum) 
{ 
    if(l==n){//only one sub-array 
     sum = Sumof(X[1:n]); 
     k=1; 
    } 
    int kl, kr; 
    float sum_l, sum_r; 
    FixedLengthMS(X[1:(n+l-1)/2], l, kl, sum_l); 
    FixedLengthMS(X[(n-l+3)/2:n], l, kr, sum_r); 

    if(sum_l >= sum_r){ 
     sum = sum_l; 
     k = kl; 
    } 
    else{ 
     sum = sum_r; 
     k = n-l+1/2 + kr; 
    } 
} 

Remarque: pour effacer l'indexation de tableau pour sous-ensemble à partir de (n-l + 1)/2 nous avons besoin d'éléments de tableau mis à (n-l + 1)/2 + l-1 = (n + l-1)/2

Mon souci: Pour appliquer diviser et vaincre j'ai utilisé quelques éléments de données dans les deux tableaux, donc je cherche une autre méthode qui évite le stockage supplémentaire.

Une méthode plus rapide sera appréciée.

S'il vous plaît ignorer la syntaxe de la section de code, j'essaie juste de donner une vue d'ensemble de l'algorithme.

Answer 1

Vous n'avez pas besoin de diviser pour régner. Un algorithme simple à un passage peut être utilisé pour la tâche. Supposons que ce tableau est assez grand. Puis:

double sum = 0; 
for (size_t i = 0; i < l; ++i) 
    sum += X[i]; 

size_t max_index = 0; 
double max_sum = sum; 

for (int i = 0; i < n - l; ++i) { 
    sum += X[i + l] - X[i]; 
    if (sum > max_sum) { 
     max_sum = sum; 
     max_index = i; 
    } 
}