8
votes

Maximiser la somme de somme pour un tableau entier

Compte tenu d'un réseau entier A, renvoyez la somme maximale possible entre deux éléments. La distance de somme est définie comme a [i] + a [j] + (i-j) pour i> j

Par exemple avec A = [8, 2, 4, 9, 5, 8, 0, 3, 8, 2] La distance maximale est atteinte avec i = 0 et j = 8

Un o ( N ^{2 ) est trivial. Y a-t-il une solution O ( n ) (où n est la longueur de la matrice)?}


                        
                        
                            
                                                                    algorithm
                                                            
                        
                                                    
                            
                            
                                6 commentaires
                                
                                                                            Bien sûr, comme  max (a [i] + i pour i dans la plage (len (a)) + max (a [j] - j pour j dans la plage (len (a))) . Ensuite Je vous regarde éditer dans la valeur absolue ou la restriction que  i , puis je vais trouver le duplicata.

                                        
                                                                            @Davideisenstat fait-il même une différence? Cela semble être si je suis négatif, il y a une meilleure solution avec I et J Swed. Dans ce cas, je pense que nous pouvons toujours le marquer comme un duplicata, si ce n'est pas trop d'effort en trouvant un
                                        
                                                                            @Niklasb. Eh bien, a été posé avant mais pas répondu:  Stackoverflow.com/Questtions/31139032/... . Dupe fera-t-il de près celui-ci.
                                        
                                                                            @Niklasb. Il y a une autre version où l'objectif ne se sépare pas si facilement - peut-être  a [i] + a [j] - | i - j | . Je me souviens de répondre à cette question.

                                        
                                                                            La question serait plus claire avec un exemple. S'il vous plaît pourriez-vous partager un exemple?
                                        
                                                                            @Niklasb.  i> j  peut faire une différence car il interdit  i == j  nous ne pouvons donc pas optimiser f (i) et h (j) indépendamment

4 Réponses : 11 votes Pour chaque index I, il suffit de connaître un index code> qui optimise la somme A [i] + a [index] + (index i-index) = A [I] + i + (un [index] - index) code>. Ce qui signifie, nous n'avons besoin que de maintenir un index code> code>, lequel a [index] - index code> est maximum. int index = 0; int result = 0; for(int i = 1; i < n; i++){ int total = A[i] + i + A[index] - index; result = max(result, total); if(A[i] - i > A[index] - index){ index = i; } } return result; 4 commentaires Vous ne pouvez pas considérer sérieusement une solution qui stocke deux matrices géantes mieux que une solution qui suit un entier. @Stef cela dépend de l'utilisation. Quoi qu'il en soit, ils sont fondamentalement la même approche, une plus utile pour d'énormes tableaux dans l'ordre 10 ^ 6, l'autre mieux débutable. Comme il n'a pas mentionné qu'il devait passer par des tableaux massives, j'ai écrit la version debommable. @xxliolUXX ayant un tableau supplémentaire ne signifie pas mieux déboguer. Je n'ai pas répondu que votre code suppose que le résultat est au moins 0 - Je ne vois pas cela dans les spécifications de problèmes. 7 votes Ceci est possible: Créez un tableau et remplissez-le avec un [i] + i pour chaque Créez un autre tableau et remplissez-le avec un [J] - J pour chaque J Obtenez les index avec le plus élevé I [maxi] et j [maxj] retourne [maxi] + a [maxj] + maxi - maxj Voilà, O (N)! 9 commentaires Pourriez-vous élaborer à la deuxième dernière étape. Pas besoin de créer de nouveaux tableaux FWIW @Niklas Droite, pas besoin de deux tableaux, mais c'est un code beaucoup plus lisible, et vous pouvez le déboguer mieux si vous trouvez une erreur un point. Donc, à moins que vous n'ayez vraiment besoin de calculer que maximum 100'000'000, vous n'aurez pas besoin de faire des micro-optimisations qui gâchent votre code. @Sumet Voir la poste éditée. Juste boucle à travers ces nouveaux tableaux pour trouver l'index avec la valeur maximale. Cette solution a deux défauts principaux, tout d'abord, vous avez besoin de deux tableaux pour stocker des données inutiles lorsqu'il n'a besoin que de deux index maxi et maxj , deuxième, cette solution donnera une mauvaise réponse, Lorsque maxj> maxi , la réponse de la paire (maxi, maxj) doit être A [maxi] + a [maxj] + maxj - maxi . Et il ne peut pas gérer le cas lorsque maxi = maxj Troisièmement, pouvez-vous démontrer comment cette solution peut être mieux débogué? Premièrement: c'est la raison pour laquelle vous pouvez le déboguer mieux! Vous voulez savoir d'où viennent les erreurs s'il y en a! Deuxièmement: je ne vois pas de problème là-bas, cela fonctionnera très bien, il n'ya pas de manipulation spéciale de cas nécessaire selon le poste. Troisième => Voir d'abord Alors, comment gérez-vous le cas A = [1,1 100]? maxi = 2 et maxj = 2? La raison pour laquelle votre solution peut mieux déboguer est d'avoir un tableau supplémentaire? Je ne comprends pas? Pouvez-vous expliquer plus? Ok, point pour vous, puisque l'OP a demandé deux éléments ... Néanmoins, oui, il est mieux débugable, car vous pouvez regarder les matrices réelles qu'il utilisait pour calculer les trucs. Quoi qu'il en soit, vous recevez mon vote car votre code semble être parfaitement amené (en dehors de la suggestion Stefs) 5 votes Merveilleux Soln ... Pham ... merci. Plus lisible Soln pourrait être ... int sumP = Integer.MIN_VALUE; int sumQ = Integer.MIN_VALUE; for(int i = 0; i < A.length; i++){ sumP = Math.max(A[i] - i, sumP); sumQ = Math.max(A[i] + i, sumQ); } return sumP + sumQ; 1 commentaires Excellente réponse Pouvez-vous s'il vous plaît élaborer? 1 votes Il s'agit de la méthode de résolution la plus précise qui a passé le test à 100% .` var sumP = MIN_VALUE*2; var sumQ = MIN_VALUE*2; for(var i = 0; i < A.length; i++){ sumP = Math.max(A[i] - i, sumP); sumQ = Math.max(A[i] + i, sumQ); } return sumP + sumQ; 1 commentaires Désolé que quand j'ai édité, je n'ai pas remarqué que c'était en JavaScript. Je pensais à Java. Et aucun moyen de modifier, car il affirme "modifier doit être plus long que 6 caractères." Alors s'il vous plaît inverser à la version que vous avez eue. Encore pardon.

Articles qui pourrait vous intéresser : Calculer la différence dans l'échelle d'évaluation alphabétique Complexité de Trouver tous les multiples de 3 et 5 entre 1 et 10 000 000 Ma vérification pour savoir si un graphique est un arbre binaire renvoie toujours faux Comment trouver le nombre d'itérations de l'algorithme de recherche binaire?