Course maximale entre des éléments identiques

24

Il s'agit d'une refonte de cette question maintenant supprimée par ar kang . Si le PO de cette question souhaite récupérer cette question ou a un problème avec moi en postant cela, je serais heureux de répondre

Étant donné une liste d'entiers en entrée, trouvez la somme maximale possible d'une sous-liste continue qui commence et se termine avec la même valeur. Les sous-listes doivent être d'une longueur d'au moins 2. Par exemple pour la liste

[1, 2, -2, 4, 1, 4]

Il existe 2 sous-listes continues différentes commençant et se terminant avec la même valeur

[1,2,-2,4,1] -> 6
[4,1,4]      -> 9

La somme la plus élevée étant 9, vous produisez 9.

Vous pouvez supposer que chaque entrée contient au moins 1 doublon.

Il s'agit de code-golf donc les réponses seront notées en octets avec moins d'octets mieux.

Cas de test

[1,2,-2,4,1,4]  -> 9
[1,2,1,2]       -> 5
[-1,-2,-1,-2]   -> -4
[1,1,1,8,-1,8]  -> 15
[1,1,1,-1,6,-1] -> 4
[2,8,2,-3,2]    -> 12
[1,1,80]        -> 2
[2,8,2,3,2]     -> 17
code-golf number array-manipulation Assistant de blé
la source
Doit [2,8,2,3,2]être 12 ou 17? Je présume 17.
NikoNyrh
@NikoNyrh Cela devrait être 17.
Wheat Wizard
Hourra pour CC BY / SA. Vous avez le droit de publier une question dérivée d'une autre, même si elle serait ultérieurement signalée comme dupe par les membres de la communauté. Il semble que vous devriez ajouter un lien vers la page du PO que je reçois de ce blog. "3. Montrez les noms des auteurs pour chaque question et répondez [...] 4. Créez un lien hypertexte avec chaque nom d'auteur directement sur leur page de profil utilisateur sur le site source" - Je n'ai pas le privilège de voir les questions supprimées, donc je ne sais pas qui a fait l'original.
Mindwin
@Mindwin Merci, j'ai ajouté un lien vers la page du PO. Je l'ai laissé à l'origine parce que je pensais que si le PO supprimait son message, il voudrait peut-être éviter d'être lié à la question.
Wheat Wizard
La raison de la suppression n'est pas pertinente et n'est pas transparente pour l'utilisateur commun (moi). Mais l'attribution est de type opt-out. En soumettant et en acceptant la licence, ils nous ont accordé ces droits dans ces conditions. Tout ce qui est en dehors est une exception. GJ.
Mindwin

Réponses:

9

Haskell , 62 octets

f prend une liste d'entiers et retourne un entier.

f l=maximum[x+sum m-sum n|x:m<-t l,y:n<-t m,x==y]
t=scanr(:)[]

Essayez-le en ligne!

Comment ça marche

  • t est la norme "obtenir tous les suffixes d'une liste sans importer Data.List.tails ".
  • Dans f l, la compréhension de la liste parcourt tous les suffixes non vides de la liste d'arguments l, avec le premier élémentx et le reste m.
  • Pour chacun, il fait de même pour tous les suffixes non vides de m, sélectionnant le premier élémenty et le reste n.
  • Si xet ysont égaux, la compréhension de la liste comprend la somme des éléments entre eux. Cette sous-liste est identique x:mà son suffixe nsupprimé, de sorte que la somme peut être calculée comme suit x+sum m-sum n.
Ørjan Johansen
la source
8

JavaScript (ES6), 68 62 octets

a=>a.map(m=(x,i)=>a.map((y,j)=>m=j<=i||(x+=y)<m|y-a[i]?m:x))|m

Cas de test

Afficher l'extrait de code

Commenté

a =>                    // a = input array
  a.map(m =             // initialize m to a function (gives NaN in arithmetic operations)
    (x, i) =>           // for each entry x at position i in a:
    a.map((y, j) =>     //   for each entry y at position j in a:
      m =               //     update m:
        j <= i ||       //       if j is not after i
        (x += y) < m |  //       or the sum x, once updated, is less than m
        y - a[i] ?      //       or the current entry is not equal to the reference entry:
          m             //         let m unchanged
        :               //       else:
          x             //         update m to the current sum
    )                   //   end of inner map()
  ) | m                 // end of outer map(); return m
Arnauld
la source
J'ai été légèrement confus par la commande de y - a[i]et (x += y) < m- à mon humble avis, le code serait légèrement plus clair avec eux échangés, car il ressemble alors à un simple golf de (x += y) < m || y != a[i].
Neil
@Neil Je vois votre point mais (x+=y)<m|y-a[i]pourrait (x+=y)<(m|y-a[i])tout aussi bien être mal interprété . Je ne suis pas sûr que cela supprimerait vraiment l'ambiguïté. (Modifié quand même car j'ai tendance à préférer cette version.)
Arnauld
Eh bien, cela suppose qu'ils ne se méprendraient pas y-a[i]|(x+=y)<mcomme (y-a[i]|(x+=y))<m...
Neil
5

Gelée , 12 octets

ĠŒc€Ẏr/€ịḅ1Ṁ

Essayez-le en ligne!

Comment ça marche

ĠŒc€Ẏr/€ịḅ1Ṁ  Main link. Argument: A (array)

Ġ             Group the indices of A by their corresponding values.
 Œc€          Take all 2-combinations of grouped indices.
    Ẏ         Dumps all pairs into a single array.
     r/€      Reduce each pair by range, mapping [i, j] to [i, ..., j].
        ị     Index into A.
         ḅ1   Convert each resulting vector from base 1 to integer, effectively
              summing its coordinates.
           Ṁ  Take the maximum.
Dennis
la source
5

Husk , 10 octets

▲mΣfΓ~€;ṫQ

Essayez-le en ligne!

Explication

▲mΣfΓ~€;ṫQ  Input is a list, say x=[1,2,-2,4,1,4]
         Q  Slices: [[1],[2],[1,2],..,[1,2,-2,4,1,4]]
   f        Keep those that satisfy this:
    Γ        Deconstruct into head and tail, for example h=2 and t=[-2,4,1]
        ;    Wrap h: [2]
      ~€     Is it an element of
         ṫ   Tails of t: [[-2,4,1],[4,1],[1]]
            Result: [[1,2,-2,4,1],[4,1,4]]
 mΣ         Map sum: [6,9]
▲           Maximum: 9
Zgarb
la source
3

R , 108 103 90 88 83 octets

function(l)max(combn(seq(l),2,function(x)"if"(rev(p<-l[x[1]:x[2]])-p,-Inf,sum(p))))

Essayez-le en ligne!

combnfrappe encore! Génère au moins toutes les sous-listes de longueur 2, définit la somme des sous- listes sur-Inf si la première et la dernière ne sont pas égales et prend le maximum de toutes les sommes.

Le "if"va déclencher un tas d'avertissements, mais ils peuvent être ignorés en toute sécurité - c'est probablement le meilleur tour de golf ici, rev(p)-pest zéro dans le premier élément ssi p[1]==tail(p,1), et "if"utilise le premier élément de son état avec un avertissement.

Giuseppe
la source
2

Gelée , 13 , 12 octets

=ṚṖḢ
ẆÇÐfS€Ṁ

Essayez-le en ligne!

Un octet enregistré par M. Xcoder, qui est actuellement en compétition avec moi. :RÉ

Explication:

        # Helper link:
=Ṛ      # Compare each element of the list to the element on the opposite side (comparing the first and last)
  Ṗ     # Pop the last element of the resulting list (so that single elements return falsy)
   Ḣ    # Return the first element of this list (1 if the first and last are equal, 0 otherwise)

        # Main link:
Ẇ       # Return every sublist
 Ç      # Where the helper link
  Ðf    # Returns true (1)
    S€  # Sum each resulting list
      Ṁ # Return the max
DJMcMayhem
la source
1

Pyth, 15 octets

eSsMf&qhTeTtT.:

Essayez-le en ligne

Explication

eSsMf&qhTeTtT.:
             .:Q  Take all sublists of the (implicit) input.
    f qhTeT       Take the ones that start and end with the same number...
     &     tT     ... and have length at least 2.
  sM              Take the sum of each.
eS                Get the largest.

la source
1

05AB1E , 9 octets

ŒʒćsθQ}OZ

Essayez-le en ligne!

Explication

Π         # push sublists of input
 ʒ    }    # filter, keep values where
  ć        # the head of the list, extracted
     Q     # is equal to
   sθ      # the last element of the rest of the list
       O   # sum the resulting sublists
        Z  # get the max
Emigna
la source
1

Propre , 94 90 86 octets

import StdEnv,StdLib
@l=last(sort[sum(l%(i,j))\\e<-l&i<-[0..],j<-elemIndices e l|j>i])

Essayez-le en ligne!

Οurous
la source
Je crains que cela échoue pour le [1, 1, 80]cas de test.
Ørjan Johansen
@ ØrjanJohansen l'a corrigé
Οurous
1

Python 2 , 86 octets

Dépassé par Dennis

lambda x:max(sum(x[i:j+1])for i,v in enumerate(x)for j in range(i+1,len(x))if v==x[j])

Essayez-le en ligne!

Génère toutes les sous-listes supérieures à la longueur 2, où le premier élément est égal au dernier, puis mappe chacune à sa somme et sélectionne la plus grande valeur.

FlipTack
la source
88 octets utilisant une fonction lambda
Halvard Hummel
@HalvardHummel 86 octets utilisant enumerate.
Jonathan Frech
Dépassé par Dennis - Honnêtement, à quoi vous attendiez-vous?
M. Xcoder
@ Mr.Xcoder J'aurais eu sa solution, mais je me suis endormi :(
FlipTack
1

Gelée , 11 octets

Utilise certaines fonctionnalités postérieures au défi.

Ẇµ.ịEȧḊµƇ§Ṁ

Essayez-le en ligne!

Comment ça marche?

Ẇµ.ịEȧḊµƇ§Ṁ || Programme complet. Prend entrée de CLA, sorties vers STDOUT.
Ẇ || Sous-listes.
 µ µƇ || Filtrez-les
    ȧḊ || ... qui ont une longueur d'au moins 2 et ...
 .ị || ... Les éléments au sol (0,5) et au plafond (0,5) (modulaire, 1 index) ...
    E || ... Sont égaux.
         § || Additionnez chacun.
          Ṁ || Maximum.

-1 avec l'aide de caird .

M. Xcoder
la source
0

Lot, 179 octets

@set s=%*
@set/a"m=-1<<30
:l
@set/at=n=%s: =,%
@set s=%s:* =%
@for %%e in (%s%)do @set/at+=%%e&if %%e==%n% set/a"m+=(m-t)*(m-t>>31)
@if not "%s%"=="%s: =%" goto l
@echo %m%

Prend l'entrée comme paramètres de ligne de commande.

Neil
la source
0

C, 104 octets

i,j,s,l;f(a,n)int*a;{for(i=0,l=1<<31;i<n;++i)for(s=a[j=i];++j<n;l=a[j]-a[i]?l:s>l?s:l)s+=a[j];return l;}

Essayez-le en ligne!

C (gcc) , 99 octets

i,j,s,l;f(a,n)int*a;{for(i=0,l=1<<31;i<n;++i)for(s=a[j=i];++j<n;l=a[j]-a[i]?l:s>l?s:l)s+=a[j];l=l;}

Essayez-le en ligne!

Steadybox
la source
99 octets , si vous aimez le comportement non défini.
Jonathan Frech
0

Clojure, 92 octets

#(apply max(for[i(range(count %))j(range i):when(=(% i)(% j))](apply +(subvec % j(inc i)))))
NikoNyrh
la source
0

Java 8, 129 byes

a->a.stream().map(b->a.subList(a.indexOf(b),a.lastIndexOf(b)+1).stream().mapToLong(Long::intValue).sum()).reduce(Long::max).get()

Pour chaque entier Xde la liste, la fonction recherche la somme de la plus grande sous-liste avec début et fin X. Ensuite, il trouve la somme maximale comme l'OP le spécifie.

Mario Ishac
la source
Je ne l'ai pas testé, mais il me semble que cela pourrait échouer dans le [2,8,2,-3,2]cas de test, et peut-être [1,1,80]aussi.
Ørjan Johansen
0

Perl, 61 59 octets

Comprend +3pour -p:

max_ident_run.pl:

#!/usr/bin/perl -p
s:\S+:$%=$&;($%+=$_)<($\//$%)||$_-$&or$\=$%for<$' >:eg}{

Courir comme:

max_ident_run.pl <<< "1 2 -2 4 1 4 1"
Ton Hospel
la source