. Somme maximale des sous-tableaux qui se chevauchent

689. Somme maximale de 3 sous-tableaux qui ne se chevauchent pas

Difficulté : Difficile

Sujets :Array, programmation dynamique

Étant donné un tableau d'entiers nums et un entier k, trouvez trois sous-tableaux qui ne se chevauchent pas de longueur k avec une somme maximale et renvoyez-les.

Renvoyer le résultat sous forme de liste d'indices représentant la position de départ de chaque intervalle (0-indexé). S'il y a plusieurs réponses, renvoyez la plus petite lexicographiquement.

Exemple 1 :

• Entrée : nums = [1,2,1,2,6,7,5,1], k = 2
• Sortie : [0,3,5]
• Explication : Les sous-tableaux [1, 2], [2, 6], [7, 5] correspondent aux indices de départ [0, 3, 5].
  • Nous aurions également pu prendre [2, 1], mais une réponse de [1, 3, 5] serait lexicographiquement plus grande.

Exemple 2 :

• Entrée : nums = [1,2,1,2,1,2,1,2,1], k = 2
• Sortie : [0,2,4]

Contraintes :

• 1 <= nums.length <= 2 * 10⁴
• 1 <= nums[i] < 2¹⁶
• 1 <= k <= étage(nums.length / 3)

Solution :

Nous utiliserons une approche de programmation dynamique. L'idée est de décomposer le problème en sous-problèmes plus petits, en tirant parti du chevauchement des sous-tableaux pour calculer efficacement la somme maximale de trois sous-tableaux non chevauchants de longueur k.

Approche:

1. Précalculez les sommes des sous-tableaux de longueur k :
   Tout d’abord, nous calculons la somme de tous les sous-tableaux de longueur k dans le tableau d’entrée nums. Cela peut être fait efficacement en temps linéaire en utilisant une technique de fenêtre glissante.

2. Programmation dynamique (DP) :
   Nous créons deux tableaux auxiliaires, gauche et droite, pour stocker les indices des meilleurs sous-tableaux trouvés jusqu'à la position actuelle. Le left[i] stockera l'index du meilleur sous-tableau se terminant avant l'index i, et le right[i] stockera l'index du meilleur sous-tableau commençant après l'index i.

3. Itérer et calculer la somme maximale :
   Pour chaque sous-tableau intermédiaire possible commençant à l'index j, nous calculons la somme totale en considérant le meilleur sous-tableau gauche avant j et le meilleur sous-tableau droit après j.

4. Ordre lexicographique :
   S'il y a plusieurs réponses valides (avec la même somme), nous renvoyons la plus petite lexicographiquement. Ceci est assuré par l'ordre d'itération.

Implémentons cette solution en PHP : 689. Somme maximale de 3 sous-tableaux qui ne se chevauchent pas

<?php
/**
 * @param Integer[] $nums
 * @param Integer $k
 * @return Integer[]
 */
function maxSumOfThreeSubarrays($nums, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
print_r(maxSumOfThreeSubarrays([1,2,1,2,6,7,5,1], 2)); // [0, 3, 5]
print_r(maxSumOfThreeSubarrays([1,2,1,2,1,2,1,2,1], 2)); // [0, 2, 4]
?>




<h3>
  
  
  Explication:
</h3>

<ol>
<li>
<p><strong>Calcul des sommes des sous-tableaux :</strong></p>

<ul>
<li>Nous calculons la somme de tous les sous-tableaux possibles de longueur k. Cela se fait en calculant d’abord la somme des k premiers éléments. Ensuite, pour chaque position suivante, nous soustrayons l'élément laissé et ajoutons l'élément suivant dans le tableau, ce qui en fait une approche de fenêtre coulissante efficace.</li>
</ul>
</li>
<li>
<p><strong>Tableaux gauche et droit :</strong></p>

<ul>
<li>
left[i] contient l'index du sous-tableau avec la somme maximale qui se termine avant l'index i.</li>
<li>
right[i] contient l'index du sous-tableau avec la somme maximale qui commence après l'index i.</li>
</ul>
</li>
<li>
<p><strong>Calcul final :</strong></p>

<ul>
<li>Pour chaque sous-tableau du milieu j, nous vérifions la combinaison du meilleur sous-tableau gauche et du meilleur sous-tableau droit, et mettons à jour le résultat si la somme est supérieure au maximum actuel.</li>
</ul>
</li>
<li>
<p><strong>Réponse lexicographiquement la plus petite :</strong></p>

<ul>
<li>En itérant de gauche à droite, nous garantissons la solution lexicographiquement la plus petite en choisissant naturellement les premiers sous-tableaux qui donnent la somme maximale.</li>
</ul>
</li>
</ol>

<h3>
  
  
  Exemple:
</h3>

<p>Pour la saisie :<br>
</p>

<pre class="brush:php;toolbar:false">$nums = [1, 2, 1, 2, 6, 7, 5, 1];
$k = 2;

Le résultat sera :

[0, 3, 5]

Cette approche garantit que la complexité temporelle reste efficace, avec une complexité temporelle d'environ O(n), où n est la longueur des nombres du tableau d'entrée.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :

• LinkedIn
• GitHub

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!