Maximaler Lauf zwischen identischen Elementen

24

Dies ist eine Überarbeitung dieser nun gelöschten Frage von ar kang . Wenn das OP dieser Frage diese Frage zurückfordern möchte oder ein Problem mit dem Posten dieser Frage hat, würde ich mich freuen, darauf eingehen zu können

Wenn Sie eine Liste von Ganzzahlen als Eingabe angeben, ermitteln Sie die maximal mögliche Summe einer fortlaufenden Unterliste, die mit demselben Wert beginnt und endet. Die Unterlisten müssen mindestens 2 lang sein. Zum Beispiel für die Liste

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

Es gibt 2 verschiedene fortlaufende Unterlisten, die mit demselben Wert beginnen und enden

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

Die größere Summe ist 9, sodass Sie 9 ausgeben.

Sie können davon ausgehen, dass jede Eingabe mindestens 1 Duplikat enthält.

Dies ist Codegolf, daher werden die Antworten in Bytes bewertet, wobei weniger Bytes besser sind.

Testfälle

[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 Weizen-Assistent
quelle
Sollte [2,8,2,3,2]12 oder 17 sein? Ich
nehme an
@NikoNyrh Es sollte 17.
Wheat Wizard
Ein Hoch auf CC BY / SA. Sie haben das Recht, eine abgeleitete Frage einer anderen zu posten, auch wenn diese später von Community-Mitgliedern als betrogen markiert wird. Es scheint nur, dass Sie einen Link zur Seite des OP hinzufügen sollten , wie ich von diesem Blog-Beitrag bekomme. "3. Zeigen Sie die Namen der Autoren für jede Frage und Antwort an. [...] 4. Verknüpfen Sie die Namen der Autoren direkt mit ihren Benutzerprofilseiten auf der Quellwebsite." - Ich habe keine Berechtigung zum Anzeigen gelöschter Fragen weiß nicht, wer das Original gemacht hat.
Mindwin
@ Mindwin Danke, ich habe einen Link zur Seite des OP hinzugefügt. Ich habe es ursprünglich weggelassen, weil ich herausgefunden habe, dass die OP ihren Beitrag gelöscht haben, um zu vermeiden, mit der Frage verknüpft zu werden.
Weizen-Assistent
Der Grund für das Löschen ist irrelevant und für den gemeinsamen Benutzer (mich) nicht transparent. Es handelt sich jedoch um eine Opt-out-Zuschreibung. Mit der Einreichung und Zustimmung zur Lizenz gewährten sie uns diese Rechte unter diesen Bedingungen. Alles außerhalb ist eine Ausnahme. GJ.
Mindwin

Antworten:

9

Haskell , 62 Bytes

f Nimmt eine Liste von ganzen Zahlen und gibt eine ganze Zahl zurück.

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

Probieren Sie es online!

Wie es funktioniert

  • tist die Standardfunktion "Alle Suffixe einer Liste abrufen, ohne sie zu importieren Data.List.tails".
  • In f ldurchläuft das Listenverständnis alle nicht leeren Suffixe der Argumentliste lmit dem ersten Element xund dem Rest m.
  • Dies gilt für alle nicht leeren Suffixe von m, wobei das erste Element yund der Rest ausgewählt werden n.
  • Wenn xund ygleich sind, enthält das Listenverständnis die Summe der Elemente zwischen ihnen. Diese Unterliste ist die gleiche wie x:mmit dem Suffix nentfernt, so dass die Summe berechnet werden kann als x+sum m-sum n.
Ørjan Johansen
quelle
8

JavaScript (ES6), 68 62 Bytes

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

Testfälle

Code-Snippet anzeigen

Kommentiert

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
quelle
Ich war ein wenig verwirrt von der Bestellung y - a[i]und (x += y) < m- meiner Meinung nach würde der Code etwas klarer mit ihnen ausgetauscht werden, seitdem sieht es aus wie ein einfacher Golf aus (x += y) < m || y != a[i].
Neil
@Neil Ich verstehe deinen Standpunkt aber (x+=y)<m|y-a[i]könnte genauso gut falsch interpretiert werden (x+=y)<(m|y-a[i]). Ich bin mir nicht sicher, ob es die Mehrdeutigkeit wirklich beseitigen würde. (Trotzdem bearbeitet, weil ich diese Version eher bevorzuge.)
Arnauld
Nun, das setzt voraus, dass sie nicht falsch interpretieren y-a[i]|(x+=y)<mals (y-a[i]|(x+=y))<m...
Neil
5

Gelee , 12 Bytes

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

Probieren Sie es online!

Wie es funktioniert

ĠŒ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
quelle
5

Schale , 10 Bytes

▲mΣfΓ~€;ṫQ

Probieren Sie es online!

Erläuterung

▲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
quelle
3

R , 108 103 90 88 83 Bytes

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

Probieren Sie es online!

combnschlägt wieder zu! Generiert mindestens alle Unterlisten der Länge 2, setzt die Unterlistensumme auf, -Infwenn die erste und die letzte nicht gleich sind, und nimmt das Maximum aller Summen.

Die "if"werden eine Reihe von Warnungen auslösen, aber sie sind sicher ignorierbar - das ist wahrscheinlich der beste Golf-Trick hier, rev(p)-pist Null im ersten Element iffp[1]==tail(p,1) und "if"verwendet das erste Element seines Zustands mit einer Warnung.

Giuseppe
quelle
2

Jelly , 13 , 12 Bytes

=ṚṖḢ
ẆÇÐfS€Ṁ

Probieren Sie es online!

Ein Byte, das von Mr. Xcoder gespeichert wurde, der gerade mit mir konkurriert. : D

Erläuterung:

        # 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
quelle
1

Pyth, 15 Bytes

eSsMf&qhTeTtT.:

Probieren Sie es online aus

Erläuterung

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.

quelle
1

05AB1E , 9 Bytes

ŒʒćsθQ}OZ

Probieren Sie es online!

Erläuterung

Π         # 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
quelle
1

Sauber , 94 90 86 Bytes

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

Probieren Sie es online!

Οurous
quelle
Ich fürchte, dies schlägt für den [1, 1, 80]Testfall fehl .
Ørjan Johansen
@ ØrjanJohansen reparierte es
Οurous
1

Python 2 , 86 Bytes

Von Dennis überfordert

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])

Probieren Sie es online!

Generiert alle Unterlisten mit einer Länge von mehr als 2, wobei das erste Element dem letzten Element entspricht, ordnet jedes Element seiner Summe zu und wählt den größten Wert aus.

FlipTack
quelle
88 Bytes mit einer Lambda-Funktion
Halvard Hummel
@ HalvardHummel 86 Bytes mit enumerate.
Jonathan Frech
Outgolfed by Dennis - Ehrlich gesagt, was haben Sie erwartet?
Mr. Xcoder
@ Mr.Xcoder Ich hätte seine Lösung bekommen, aber ich ging schlafen :(
FlipTack
1

Jelly , 11 Bytes

Verwendet einige Funktionen, die die Herausforderung nachholen.

Ẇµ.ịEȧḊµƇ§Ṁ

Probieren Sie es online!

Wie es funktioniert?

Ẇµ.ịEịµȧḊ§Ƈ || Volles Programm. Übernimmt die Eingabe von CLA und gibt sie an STDOUT aus.
Ẇ || Unterlisten.
 µ µƇ || Filter-Keep diejenigen
    ȧḊ || ... die mindestens 2 länge haben und ...
 .ị || ... Die Elemente am Boden (0,5) und an der Decke (0,5) (modular, 1-indiziert) ...
    E || ... Sind gleich.
         § || Summe jeweils.
          Ṁ || Maximal.

-1 mit Hilfe von Caird .

Mr. Xcoder
quelle
0

Stapel, 179 Bytes

@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%

Übernimmt Eingaben als Befehlszeilenparameter.

Neil
quelle
0

C 104 Bytes

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;}

Probieren Sie es online!

C (gcc) , 99 Bytes

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;}

Probieren Sie es online!

Steadybox
quelle
99 Bytes , wenn Sie undefiniertes Verhalten mögen.
Jonathan Frech
0

Clojure, 92 Bytes

#(apply max(for[i(range(count %))j(range i):when(=(% i)(% j))](apply +(subvec % j(inc i)))))
NikoNyrh
quelle
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()

Für jede Ganzzahl Xin der Liste ermittelt die Funktion die Summe der größten Unterliste mit Anfang und Ende X. Dann wird die maximale Summe ermittelt, wie vom OP angegeben.

Mario Ishac
quelle
Ich habe es nicht getestet, aber für mich sieht es so aus, als ob es im [2,8,2,-3,2]Testfall fehlschlagen könnte , und möglicherweise [1,1,80]auch.
Ørjan Johansen
0

Perl, 61 59 Bytes

Beinhaltet +3für -p:

max_ident_run.pl:

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

Rennen wie:

max_ident_run.pl <<< "1 2 -2 4 1 4 1"
Tonne Hospel
quelle