Je suis la Grande Matrice

1975. Somme matricielle maximale

Difficulté :Moyen

Sujets :Array, Greedy, Matrix

Vous recevez une matrice entière n x n. Vous pouvez effectuer l'opération suivante un certain nombre de fois :

• Choisissez deux éléments adjacents quelconques de la matrice et multipliez chacun d'eux par -1.

Deux éléments sont considérés adjacents si et seulement s'ils partagent une frontière.

Votre objectif est de maximiser la somme des éléments de la matrice. Renvoie la somme maximale des éléments de la matrice en utilisant l'opération mentionnée ci-dessus.

Exemple 1 :

• Entrée : matrice = [[1,-1],[-1,1]]
• Sortie : 4
• Explication : Nous pouvons suivre les étapes suivantes pour atteindre une somme égale à 4 :
  • Multipliez les 2 éléments de la première ligne par -1.
  • Multipliez les 2 éléments de la première colonne par -1.

Exemple 2 :

• Entrée : matrice = [[1,2,3],[-1,-2,-3],[1,2,3]]
• Sortie : 16
• Explication : On peut suivre l'étape suivante pour atteindre la somme est égale à 16 :
  • Multipliez les 2 derniers éléments de la deuxième ligne par -1.

Contraintes :

• n == matrice.longueur == matrice[i].longueur
• 2 <= n <= 250
• -10⁵ <= matrice[i][j] <= 10⁵

Indice :

1. Essayez d'utiliser l'opération pour que chaque ligne n'ait qu'un seul nombre négatif.
2. Si vous n'avez qu'un seul élément négatif, vous ne pouvez pas le convertir en positif.

Solution :

Pour maximiser la somme de la matrice à l'aide de l'opération, nous devons minimiser la valeur absolue des contributions négatives à la somme. Voici le plan :

1. Compter les nombres négatifs : Suivez le nombre de nombres négatifs présents dans la matrice.
2. Trouver la valeur absolue minimale : Déterminez la plus petite valeur absolue de la matrice, ce qui sera utile si le nombre de négatifs est impair.
3. Ajuster pour les négatifs impairs : Si le nombre de nombres négatifs est impair, la plus petite valeur absolue ne peut pas être transformée en positive, ce qui limite la somme maximale possible.

Implémentons cette solution en PHP : 1975. Somme matricielle maximale

  
  
  Explication:




Somme des valeurs absolues : Calculez la somme des valeurs absolues de tous les éléments puisque la configuration optimale transforme autant de nombres négatifs en positifs que possible.

Suivez la plus petite valeur absolue : Utilisez ceci pour ajuster la somme lorsque le nombre de nombres négatifs est impair.

Gérer les négatifs impairs : Soustrayez deux fois la plus petite valeur absolue de la somme pour tenir compte de l'élément négatif inévitable lorsque les négatifs ne peuvent pas être complètement neutralisés.



  
  
  Complexité




Complexité temporelle : O(n^2), car la matrice est parcourue une fois.

Complexité de l'espace : O(1), puisqu'aucun espace supplémentaire n'est utilisé en dehors des variables.


Cette solution fonctionne efficacement dans les limites données.

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!