Somme Maximale d'un Sous-tableau

La résolution de ce problème repose sur une approche gloutonne (greedy). L'idée centrale est que si la somme cumulée d'un sous-tableau devient négative, elle ne peut que diminuer la somme des éléments suivants. Par conséquent, dès que la somme courante tombe en dessous de zéro, nous réinitialisons le compteur pour repartir du prochain élément.

Logique de l'algorithme

• Optimum local : Si la somme accumulée est négative, on l'abandonne et on recommence le calcul à partir de l'élément suivant.
• Optimum global : On maintient une varible pour enregistrer la valeur maximale rencontrée par la somme accumulée au cours de l'itération complète.

public int maxSubArray(int[] nums) {
   int maxGlobal = Integer.MIN_VALUE;
   int sommeCourante = 0;
   for (int i = 0; i < nums.length; i++) {
       sommeCourante += nums[i];
       if (sommeCourante > maxGlobal) {
           maxGlobal = sommeCourante;
       }
       if (sommeCourante <= 0) {
           sommeCourante = 0; // Réinitialisation de l'optimum local
       }
   }
   return maxGlobal;
}

Fusion d'Intervalles

Pour fusionner des intervalles qui se chevauchent, la première étape indispensable est de trier les intervalles en fonction de leur borne inférieure. Une fois triés, les intervalles pouvant être fusionnés seront nécessairement adjacents dans la liste.

Implémentation technique

On utilise un comparateur personnalisé pour le tri. Pour chaque intervalle, on vérifie s'il chevauche le dernier intervalle ajouté au résultat :

• Si la borne gauche de l'intervalle actuel est supérieure à la borne droite du dernier intervalle enregistré, il n'y a pas de chevauchement. On l'ajoute tel quel.
• Sinon, il y a chevauchement. On met à jour la borne droite du dernier intervalle en prenant le maximum des deux bornes droites.

public int[][] merge(int[][] intervals) {
   if (intervals.length == 0) return new int[0][];
   
   // Tri par borne inférieure
   Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
   
   List<int[]> result = new ArrayList<>();
   result.add(intervals[0]);
   
   for (int i = 1; i < intervals.length; i++) {
       int[] lastMerged = result.get(result.size() - 1);
       if (intervals[i][0] <= lastMerged[1]) {
           lastMerged[1] = Math.max(lastMerged[1], intervals[i][1]);
       } else {
           result.add(intervals[i]);
       }
   }
   return result.toArray(new int[result.size()][]);
}

Rotasion d'un Tableau

L'objectif est de déplacer chaque élément du tableau de k positions vers la droite. Une solution simple consiste à utiliser un tableau auxiliaire pour stocker les éléments déplacés avant de les recopier dans le tableau d'origine.

La nouvelle position d'un élément à l'indice i est calculée par la formule : (i + k) % n, où n est la taille du tableau.

public void rotate(int[] nums, int k) {
   int n = nums.length;
   int[] temp = new int[n];
   for (int i = 0; i < n; i++) {
       temp[(i + k) % n] = nums[i];
   }
   System.arraycopy(temp, 0, nums, 0, n);
}

Produit d'un Tableau Sauf Soi-même

Ce problème doit être résolu sans utiliser la division. L'approche consiste à calculer pour chaque indice i le produit de tous les éléments à sa gauche et le produit de tous les éléments à sa droite.

Procédure en deux étapes

1. Produits à gauche : On parcourt le tableau de gauche à droite. L[i] contient le produit de tous les éléments de 0 à i-1.
2. Produits à droite : On parcourt le tableau de droite à gauche. R[i] contient le produit de tous les éléments de i+1 à n-1.

Le résultat final pour l'indice i est simplement L[i] * R[i].

public int[] productExceptSelf(int[] nums) {
   int len = nums.length;
   int[] left = new int[len];
   int[] right = new int[len];
   int[] res = new int[len];

   left[0] = 1;
   for (int i = 1; i < len; i++) {
       left[i] = left[i - 1] * nums[i - 1];
   }

   right[len - 1] = 1;
   for (int i = len - 2; i >= 0; i--) {
       right[i] = right[i + 1] * nums[i + 1];
   }

   for (int i = 0; i < len; i++) {
       res[i] = left[i] * right[i];
   }
   return res;
}