Maksymalny przebieg między identycznymi elementami

24

To jest przegląd tego usuniętego teraz pytania przez ar kang . Jeśli OP tego pytania chciałoby odzyskać to pytanie lub ma problem ze mną, publikując to, chętnie się z tym pogodzę

Biorąc pod uwagę listę liczb całkowitych jako danych wejściowych, znajdź maksymalną możliwą sumę ciągłej listy podrzędnej, która zaczyna się i kończy tą samą wartością. Podlisty muszą mieć długość co najmniej 2. Na przykład dla listy

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

Istnieją 2 różne ciągłe listy podrzędne, rozpoczynające się i kończące o tej samej wartości

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

Większa suma to 9, więc wyprowadzasz 9.

Możesz założyć, że każde wejście zawiera co najmniej 1 duplikat.

To jest golf golfowy, więc odpowiedzi będą liczone w bajtach, przy czym mniej bajtów będzie lepszych.

Przypadki testowe

[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 
— Kreator pszenicy
źródło
Powinien [2,8,2,3,2]mieć 12 lub 17 lat? Przypuszczam, że 17.
— NikoNyrh
@NikoNyrh Powinno być 17.
— Wheat Wizard
Brawo dla CC BY / SA. Masz prawo opublikować pytanie pochodne innego, nawet jeśli zostanie później oznaczone jako dupe przez członków społeczności. Wydaje się, że powinieneś dodać link do strony PO, jak otrzymałem z tego postu na blogu. „3. Pokaż nazwiska autorów dla każdego pytania i odpowiedz [...] 4. Hiperłącze każdego autora z powrotem bezpośrednio do strony jego profilu użytkownika w witrynie źródłowej” - nie mam uprawnień, aby zobaczyć usunięte pytania, więc nie nie wiem, kto zrobił oryginalny.
— Mindwin
@Mindwin Dzięki, dodałem link do strony PO. Pominąłem to pierwotnie, ponieważ pomyślałem, że jeśli OP usunie swój post, mogą chcieć uniknąć powiązania z pytaniem.
— Wheat Wizard
Przyczyna usunięcia jest nieistotna i nieprzejrzysta dla zwykłego użytkownika (mnie). Ale przypisanie ma charakter opt-out. Przesyłając i zgadzając się na licencję, przyznali nam te prawa na tych warunkach. Wszystko poza tym jest wyjątkiem. GJ
— Mindwin

Odpowiedzi:

9

Haskell , 62 bajty

f pobiera listę liczb całkowitych i zwraca liczbę całkowitą.

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

Wypróbuj online!

Jak to działa

  • tto standardowa funkcja „pobierz wszystkie sufiksy listy bez importowania Data.List.tails”.
  • W f linterpretacji listy iterowane są wszystkie niepuste sufiksy listy argumentów l, z pierwszym elementem xi resztą m.
  • Dla każdego robi to samo dla wszystkich niepustych sufiksów m, wybierając pierwszy element yi resztę n.
  • Jeśli xi ysą równe, lista zawiera sumę elementów między nimi. Ta lista podrzędna jest taka sama, jak x:mz nusuniętym przyrostkiem , więc sumę można obliczyć jako x+sum m-sum n.
— Ørjan Johansen
źródło
8

JavaScript (ES6), 68 62 bajtów

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

Przypadki testowe

Pokaż fragment kodu

Skomentował

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
źródło
Byłem nieco zdezorientowany kolejnością y - a[i]i (x += y) < m- IMHO kod będzie nieco wyraźniejszy przy ich wymianie, od tego czasu wygląda to jak zwykły golf (x += y) < m || y != a[i].
— Neil
@ Nee Rozumiem twój punkt widzenia, ale równie dobrze (x+=y)<m|y-a[i]może zostać źle zinterpretowany (x+=y)<(m|y-a[i]). Nie jestem pewien, czy to naprawdę pozbyłoby się dwuznaczności. (Zresztą zresztą i tak, ponieważ wolę tę wersję).
— Arnauld
Zakłada się, że nie błędnie zinterpretowaliby y-a[i]|(x+=y)<mjako (y-a[i]|(x+=y))<m...
— Neil
5

Galaretka , 12 bajtów

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

Wypróbuj online!

Jak to działa

ĠŒ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
źródło
5

Łuska , 10 bajtów

▲mΣfΓ~€;ṫQ

Wypróbuj online!

Wyjaśnienie

▲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
źródło
3

R , 108 103 90 88 83 bajtów

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

Wypróbuj online!

combnuderza ponownie! Generuje wszystkie podlisty o długości co najmniej 2, ustawia sumę podlisty na , -Infjeśli pierwsza i ostatnia nie są równe, i przyjmuje maksimum wszystkich sum.

"if"Podniesie kilka ostrzeżeń, ale są one bezpiecznie ignorable - to chyba najlepszy trik golfa tutaj, rev(p)-pwynosi zero w pierwszym elemencie IFF p[1]==tail(p,1)i "if"wykorzystuje pierwszy element jego stanu z ostrzeżeniem.

— Giuseppe
źródło
2

Galaretka , 13 , 12 bajtów

=ṚṖḢ
ẆÇÐfS€Ṁ

Wypróbuj online!

Jeden bajt zapisany przez pana Xcodera, który obecnie ze mną konkuruje. :RE

Wyjaśnienie:

        # 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
źródło
1

Pyth, 15 bajtów

eSsMf&qhTeTtT.:

Wypróbuj online

Wyjaśnienie

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.
1

05AB1E , 9 bajtów

ŒʒćsθQ}OZ

Wypróbuj online!

Wyjaśnienie

Π         # 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
źródło
1

Python 2 , 86 bajtów

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

Wypróbuj online!

Generuje wszystkie listy podrzędne o długości większej niż 2, gdzie pierwszy element jest równy ostatniemu, a następnie mapuje każdą do swojej sumy i wybiera największą wartość.

— FlipTack
źródło
88 bajtów przy użyciu funkcji lambda
— Halvard Hummel
@HalvardHummel 86 bajtów przy użyciuenumerate .
— Jonathan Frech
Outgolfed by Dennis - Szczerze mówiąc, czego się spodziewałeś?
— Pan Xcoder,
@ Mr.Xcoder Miałbym jego rozwiązanie, ale poszedłem spać :(
— FlipTack
1

Galareta , 11 bajtów

Korzysta z niektórych funkcji, które są późniejsze niż wyzwanie.

Ẇµ.ịEȧḊµƇ§Ṁ

Wypróbuj online!

Jak to działa?

Ẇµ.ịEȧḊµƇ§Ṁ || Pełny program Pobiera dane wejściowe z CLA, dane wyjściowe do STDOUT.
Ẇ || Podlisty.
 µ µƇ || Filtruj - zachowaj je
    ȧḊ || ... które mają długość co najmniej 2 i ...
 .ị || ... Elementy na podłodze (0,5) i suficie (0,5) (modułowe, 1-indeksowane) ...
    E || ... Są równe.
         § || Suma każdego.
          Ṁ || Maksymalny.

-1 z pomocą kopca .

— Pan Xcoder
źródło
0

Partia, 179 bajtów

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

Pobiera dane wejściowe jako parametry wiersza polecenia.

— Neil
źródło
0

Clojure, 92 bajty

#(apply max(for[i(range(count %))j(range i):when(=(% i)(% j))](apply +(subvec % j(inc i)))))
— NikoNyrh
źródło
0

Java 8, 129 bajtów

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

Dla każdej liczby całkowitej Xna liście funkcja znajduje sumę największej podlisty z początkiem i końcem X. Następnie znajduje maksymalną sumę, jak określa PO.

— Mario Ishac
źródło
Nie testowałem tego, ale wydaje mi się, że może się nie powieść w [2,8,2,-3,2]przypadku testowym i prawdopodobnie [1,1,80]również.
— Ørjan Johansen
0

Perl, 61 59 bajtów

Obejmuje +3dla -p:

max_ident_run.pl:

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

Uruchom jako:

max_ident_run.pl <<< "1 2 -2 4 1 4 1"
— Ton Hospel
źródło
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.