Algorithmes et Structures de Données

Conquer Maximum Sum Subarray with Divide & Conquer Algorithm

Il existe de nombreuses manières de trouver le sous-tableau de somme maximale parmi n entiers. L’une des approches pour résoudre ce problème consiste à appliquer l’algorithme de division & conquête. Pour y parvenir, on divise récursivement le tableau en 2 parties, puis on cherche la somme maximale dans la partie gauche, dans la partie droite, et dans la partie qui chevauche le point médian. Enfin, on utilise ces résultats pour déterminer la somme maximale pour le tableau courant.
Voici le pseudocode correspondant :
def max_subarray(a):
    # Base cases
    if len(a) == 0:
        return float('-inf'), float('-inf'), float('-inf')
    if len(a) == 1:
        return a[0], a[0], a[0]

    # Divide (get answers for left and right parts)
    ll, lmax, lr = max_subarray(a[:len(a) // 2])
    rl, rmax, rr = max_subarray(a[len(a) // 2:])
    lsum = sum(a[:len(a) // 2])
    rsum = sum(a[len(a) // 2:])

    # Obtain 3 numbers and return max-prefix, max-suffix, and total maximum sum
    return conquer(ll, lmax, lr, lsum, rl, rmax, rr, rsum)
Dans ce problème, il vous est demandé d’implémenter la partie conquer : étant donné 8 nombres, vous devez déterminer correctement 3 valeurs qui correspondent à la meilleure somme préfixe, à la meilleure somme recouvrant le point médian et à la meilleure somme suffixe. Les 8 nombres fournis sont :
  1. La meilleure somme préfixe pour le sous-tableau gauche
  1. La somme maximale du sous-tableau gauche
  1. La meilleure somme suffixe du sous-tableau gauche
  1. La somme de tous les nombres dans le sous-tableau gauche
  1. La meilleure somme préfixe pour le sous-tableau droit
  1. La somme maximale du sous-tableau droit
  1. La meilleure somme suffixe du sous-tableau droit
  1. La somme de tous les nombres dans le sous-tableau droit

Entrée

La seule ligne d’entrée contient 8 entiers dans l’ordre décrit ci-dessus. Tous ces entiers sont compris dans l’intervalle de valeur absolue ne dépassant pas .

Sortie

Le programme doit afficher 3 nombres : la meilleure somme préfixe, la meilleure somme recouvrant le point médian et la meilleure somme suffixe.

Exemples

Entrée
Sortie
7 13 9 6 7 9 3 -2
13 16 7
7 13 9 6 5 25 3 1
11 25 10
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue