Wprowadzenie:

Zainspirowany tymi dwoma pytaniami SO (bez wątpienia z tej samej klasy): wydrukuj elementy w podtablicy maksymalnej sumy bez sąsiadujących elementów java i Maksymalna suma nieprzylegających elementów tablicy, które zostaną wydrukowane .

Wyzwanie:

Biorąc pod uwagę listę liczb całkowitych, wypisz podsekwencję składającą się z nieprzylegających do siebie elementów o najwyższej sumie. Oto kilka przykładów:

• [1,2,3,-1,-3,2,5]spowoduje [1,3,5](z sumą 9) indeksy oparte na 0 [0,2,6].
• [4,5,4,3]spowoduje albo [4,4](z sumą 8) przy indeksach opartych na 0 [0,2]lub [5,3](również z sumą 8) przy indeksach opartych na 0 [1,3].
• [5,5,10,100,10,5]spowoduje [5,100,5](z sumą 110) indeksy oparte na 0 [0,3,5]lub [1,3,5].

Co najważniejsze w powyższych przykładach, indeksy zawierające elementy są co najmniej 2 od siebie. Jeśli przyjrzymy się dokładniej przykładowi [5,5,10,100,10,5]: mamy następującą potencjalną podsekwencję zawierającą nieprzylegające elementy; z ich indeksami poniżej; z sumami poniżej:

[[5],[10],[100],[10],[5],[5],[100,5],[10,5],[10,10],[5,5],[5,10],[5,100],[5,5],[5,10],[5,100],[5,10],[5,100,5],[5,100,5],[5,10,5],[5,10,10]]   // non-adjacent subsequences
[[5],[ 4],[  3],[ 2],[1],[0],[  3,5],[ 2,5],[ 2, 4],[1,5],[1, 4],[1,  3],[0,5],[0, 4],[0,  3],[0, 2],[1,  3,5],[0,  3,5],[0, 2,5],[0, 2, 4]]   // at these 0-based indices
[  5,  10,  100,  10,  5,  5,    105,    15,     20,   10,    15,    105,   10,    15,    105,    15,      110,      110,      20,       25]   // with these sums
                                                                                                            ^         ^                        // and these two maximums

Ponieważ maksymalne kwoty są 110, wyprowadzamy [5,100,5]jako wynik.

Zasady konkursu:

• Możesz wyprowadzać pary klucz-wartość indeksu + wartość. Zamiast tego [5,100,5]możesz wyprowadzać dane wyjściowe [[0,5],[3,100],[5,5]]lub [[1,5],[3,100],[5,5]]w wyniku (lub [[1,5],[4,100],[6,5]]/ [[2,5],[4,100],[6,5]]gdy indeksowanie oparte na 1 zamiast 0).
  • Jeśli użyjesz par klucz-wartość, mogą one również występować w kolejności odwrotnej lub losowej, ponieważ jasne jest, które wartości mają na myśli ze względu na sparowany indeks.
  • Wyprowadzanie tylko indeksów bez wartości jest niedozwolone. Powinien albo generować wartości, albo wartości / indeksy jako pary klucz-wartość (lub dwie oddzielne listy dla „kluczy” i „wartości” tego samego rozmiaru, jeśli pary klucz-wartość nie są możliwe w wybranym języku).
• Możesz wypisywać wszystkie możliwe podciągi z maksymalną sumą zamiast tylko jednej.
• Jak widać z przykładów, lista wejściowa może również zawierać wartości ujemne i zduplikowane. Możesz założyć, że liczby całkowite wejściowe są w zakresie .$[-999,999]$
• Lista wyjściowa nie może być pusta i zawsze musi zawierać co najmniej jeden element (jeśli lista zawiera tylko wartości ujemne, wówczas lista zawierająca jedną najniższą wartość ujemną byłaby wówczas wynikiem - patrz dwa ostatnie przypadki testowe).
• Jeśli istnieje jeden możliwy wynik, ale dla wielu różnych indeksów, dozwolone jest generowanie obu z nich, nawet jeśli mogą wyglądać na duplikaty. (tzn. powyższy przykład może wyprowadzać dane [[5,100,5],[5,100,5]]dla obu możliwych kombinacji indeksów).

Przypadki testowe:

Input:                   Possible outputs:       At 0-based indices:     With sum:

[1,2,3,-1,-3,2,5]        [1,3,5]                 [0,2,6]                 9
[4,5,4,3]                [4,4]/[5,3]             [0,2]/[1,3]             8
[5,5,10,100,10,5]        [5,100,5]               [0,3,5]/[1,3,5]         110
[10]                     [10]                    [0]                     10
[1,1,1]                  [1,1]                   [0,2]                   2
[-3,7,4,-2,4]            [7,4]                   [1,4]                   11
[1,7,4,-2]               [7]                     [1]                     7
[1,2,-3,-4,5,6,-7]       [2,6]                   [1,5]                   8
[800,-31,0,0,421,726]    [800,726]/[800,0,726]   [0,5]/[0,3,5]/[0,2,5]   1526
[-1,7,8,-5,40,40]        [8,40]                  [2,4]/[2,5]             48
[-5,-18,-3,-1,-10]       [-1]                    [3]                     -1
[0,-3,-41,0,-99,-2,0]    [0]/[0,0]/[0,0,0]       [0]/[3]/[6]/[0,3]/
                                                  [0,6],[3,6]/[0,3,6]    0

Łuska , 11 bajtów

►Σ†!¹mü≈tṖŀ

Wypróbuj online!

Wyjaśnienie

►Σ†!¹mü≈tṖŀ  Implicit input, say L=[4,5,3,4].
          ŀ  Indices: [1,2,3,4]
         Ṗ   Powerset: [[],[1],[2],[1,2],..,[1,2,3,4]]
        t    Tail (remove the empty list): [[1],[2],[1,2],..,[1,2,3,4]]
     m       For each,
      ü      de-duplicate by
       ≈     differing by at most 1.
             For example, [1,2,4] becomes [1,4].
  †          Deep map
   !¹        indexing into L: [[4],[5],[4],..,[5,4],[4,3]]
►            Maximum by
 Σ           sum: [5,4]

Haskell , 60 bajtów

snd.([]%)
r%(h:t)=max(r%t)$(r++[h])%drop 1t
r%_=(sum r<$r,r)

Wypróbuj online!

Funkcja pomocnicza %rekurencyjnie rozgałęzia się po wybraniu, czy dołączyć pierwszy element i upuścić drugi, czy też pominąć pierwszy element. Pobiera maksimum wszystkich wyników, którymi są krotki, których pierwszym elementem jest suma, a drugim elementem jest odpowiednia lista wyodrębniona dla wyniku.

Aby poradzić sobie z zasadą, że pusta lista jest niedozwolona, ​​nawet jeśli miałaby najmniejszą sztuczkę, wykonujemy uroczą sztuczkę pisania sum r<$rzamiast. sum rTo tworzy listę, której wszystkie elementy są sum ri których długość jest równa r. W ten sposób, kiedy wybieramy maksimum, priorytetem jest każda lista nad pustą r, ale w przeciwnym razie porównania zależą od pierwszego elementu, który jest sum r.

R , 136 125 bajtów

function(l,G=unlist(Map(combn,list(y<-seq(a=l)),y,c(function(x)'if'(all(diff(x)>1),l[x],-Inf)),F),F))G[which.max(Map(sum,G))]

Wypróbuj online!

-6 bajtów dzięki digEmAll , który, nawiasem mówiąc, również mnie obezwładnił .

Zwraca najkrótszą podsekwencję jako a list, przerywając najpierw związki leksykograficzne indeksami.

Brute-force generuje wszystkie podsekwencje indeksu, a następnie Filters dla tych, które nie sąsiadują, tj all(diff(x)>1). Gdzie . Następnie podzbiory [język lza pomocą tych wskaźników, wybierając [[pierwszy z nich, gdzie suma jest max ( which.max).

Jestem prawie pewien, że jest to pierwsza odpowiedź, jaką kiedykolwiek napisałem R, która używa Filter! smutny, Filterjest niegrzeczny, nic dziwnego, że nigdy go nie użyłem ...

05AB1E , 14 bajtów

Zaoszczędził 1 bajt dzięki Kevinowi Cruijssenowi

ā<æʒĆ¥≠W}èΣO}θ

Wypróbuj online! lub jako pakiet testowy

Wyjaśnienie

ā<               # push [0 ... len(input)-1]
  æ              # compute powerset
   ʒ    }        # filter, keep lists where:
      ≠W         # no element is 1 in the
     ¥           # deltas
    Ć            # of the list with the head appended
         è       # index into the input with each
          ΣO}    # sort by sum
             θ   # take the last element

Brachylog (v2), 14 bajtów

{~ba~c∋₁ᵐ}ᶠ+ᵒt

Wypróbuj online!

Podanie funkcji; wejście z lewej strony, wyjście z prawej strony, jak zwykle. Bardzo wolno; pięcioelementowa lista jest prawdopodobnie maksimum dla testów na TIO.

{~ba~c∋₁ᵐ}ᶠ+ᵒt
 ~b              Prepend an arbitrary element to the input
   a             Take a prefix or suffix of the resulting list
    ~c           Ordered partition into contiguous sublists
      ∋₁         Take the second element
        ᵐ          of each sublist
{        }ᶠ      Find all possible ways to do this
           +ᵒ    Sort by sum
             t   Take the greatest

Wyniki, które otrzymujemy z prefiksów, nie są niepoprawne, ale również nie są interesujące; wszystkie możliwe wyniki są generowane poprzez pobranie sufiksu (który może być samą listą, ale nie może być pusty), ale „sufiks” jest bardziej szczegółowy w Brachylogu niż „prefiks lub sufiks”, więc wybrałem wersję bardziej złożoną (i mniej wydajne, ale nadal poprawne). Podstawową ideą jest to, że dla każdego elementu, który chcemy na liście wyników, podział na ciągłe podlisty musi umieścić ten element i element wcześniej w tej samej podlistie (ponieważ element jest drugimelement listy podrzędnej), więc w wyniku nie mogą pojawić się dwa kolejne elementy. Z drugiej strony jest dość jasne, że w wyniku może pojawić się każda lista bez dwóch kolejnych elementów. Kiedy więc mamy wszystkie możliwe listy kandydatów, możemy po prostu zebrać ich sumy i zobaczyć, która z nich jest największa.

Galaretka , 16 14 bajtów

JŒPḊf’$ÐḟịµSÞṪ

Wypróbuj online!

Dzięki @EriktheOutgolfer za zapisanie 2 bajtów!

JavaScript (ES6),  138 132 130 129  126 bajtów

Generuje pary klucz-wartość.

a=>a.reduce((a,x,i)=>[...a,...a.map(y=>[[x,i],...y])],[[]]).map(m=a=>a.some(s=p=([v,i])=>p-(s=~~s+v,p=i)<2)|s<m||(r=a,m=s))&&r

Wypróbuj online!

Krok 1

$[value, index]$

a.reduce((a, x, i) => // for each value x at position i:
  [                   //   update a[] to a new array consisting of:
    ...a,             //     all previous entries
    ...a.map(y =>     //     for each value y in a[]:
      [[x, i], ...y]  //       append [x, i], followed by all original entries
    )                 //     end of map()
  ],                  //   end of new array
  [[]]                //   start with a = [[]]
)                     // end of reduce()

Krok 2

$m$$r$

.map(m =              // initialize m to a non-numeric value
  a =>                // for each entry a[] in the powerset:
  a.some(s = p =      //   initialize s and p to non numeric values
    ([v, i]) =>       //   for each value v and each index i in a[]:
    p - (             //     compute p - i
      s = ~~s + v,    //     add v to s
      p = i           //     update p to i
    ) < 2             //     if p - i is less than 2, yield true
  ) |                 //   end of some()
  s < m ||            //   unless some() was truthy or s is less than m,
  (r = a, m = s)      //   save a[] in r[] and update m to s
) && r                // end of map(); return r[]

Haskell, 81 80 bajtów

snd.maximum.map((,)=<<sum).tail.f
f(a:b:c)=f(b:c)++map(a:)(f c)
f a=[]:map(:[])a

Wypróbuj online!

fbuduje wszystkie poprawne podciągi, pomijając następny element ( f(b:c)) lub używając go i pomijając następny ( map(a:)(f c)) i rekurencyjnie pracuj nad resztą. Aby uzyskać wynik, zbuduj wszystkie podsekwencje ( f), upuść puste podsekwencje (które występują najpierw na liście tail:), twórz pary (<sum>,<subsequence>)( map((,)=<<sum)), znajdź maksimum (pary są porównywane w kolejności leksykograficznej) -> maximum) i upuść sumę ( snd).

Edycja: -1 bajt dzięki @Lynn.

J , 47 bajtów

>@{:@(<@#~/:+/@#~)1(-#~0=1 1+/@E."1-)[:i.&.#.=~

Wypróbuj online!

-7 bajtów dzięki FrownyFrog

oryginalny

J , 54 bajty

[:(>@{:@/:+/&>)]<@#~"1[:(#~0=1 1+/@E."1])[:#:@}[email protected]^#

Wypróbuj online!

T-SQL, 122 119 118 bajtów

Dane wejściowe to zmienna tabelowa.

To zapytanie wybiera wszystkie elementy ze zmiennej tabeli, łącząc je ze wszystkimi nieprzylegającymi elementami z wyższymi wartościami pozycji i pokazuje tekst wygenerowany dla najwyższej sumy tych wartości.

WITH C(y,j,v)as(SELECT*,x*1FROM @
UNION ALL
SELECT y+','+x,i,v+x
FROM @ JOIN C ON~-i>j)SELECT
TOP 1y FROM C ORDER BY-v

Wypróbuj online bez golfa

Wolfram Language (Mathematica) , 144 bajty

If[Max[a=#]>(d=Max[m=Tr/@(g=a[[#]]&/@Select[Subsets[Range[x=Length@#],{2,x}]&@#,FreeQ[Differences@#,1]&]&@a)]),{Max@a},g[[#]]&@@@Position[m,d]]&

Wypróbuj online!

Pyth, 19 bajtów

esDm@LQdtf!q#1.+TyU

Spróbuj go online tutaj , lub sprawdzić wszystkie przypadki testowe od razu tutaj .

esDm@LQdtf!q#1.+TyUQ   Implicit: Q=eval(input())
                       Trailing Q inferred
                  UQ   Generate range [0-len(Q))
                 y     Take the powerset of the above
         f             Filter keep elements of the above, as T, using:
              .+T        Take differences of consecutive elements of T
           q#1           Keep those differences equal to 1
          !              Logical NOT - empty lists evaluate to true, populated ones to false
                       Result of the filter is those sets without consecutive numbers
        t              Drop the first element (empty set)
   m                   Map the remaining sets, as d, using:
     L d                 For each element of d...
    @ Q                  ... get the element in Q with that index
 sD                    Order the sets by their sum
e                      Take the last element, implicit print

Gaia , 24 bajty

e:w;ċz⟨ọ1>¦ẏ⟩⁇‼⁇E‡ev2%Σ⌠

Wypróbuj online!

Ugh, E‡robi jakieś dziwne rzeczy ... zgodnie z dokumentacją powinien zrobić coś takiego „danej długości izestawu list Xi długość jzestawu wskaźników Y, powrotu X[i][Y[j]]”, lecz powraca [X[i][Y[j]] X[i][Y[-j]]gdzie negatywne indeksowanie oznacza dopełnienie, tak musimy zrobić, ev2%aby wyodrębnij tylko te, które chcemy.

e				| eval as a list l
 :				| dup
  w				| wrap as a list
   ;				| push l again
    ċ				| push [1..len(l)]
     z				| push all subsets of [1..len(l)] -- index powerset.
      ⟨      ⟩⁇			| filter this for:
       ọ			| deltas
        1>¦			| are greater than 1
           ẏ			| all (all deltas greater than 1)
	       ‼⁇		| filter for non-empty lists
		 E‡		| table extract elements. Given l and index set i, this pushes
				| [l[i] l[setdiff(1..l,i)]] for some reason
		   ev2%		| get the l[i] only by unlisting, reversing, and taking every other element
		       Σ⌠	| Get the one with the maximum sum

R , 108 107 bajtów

function(v,M=-Inf){for(j in J<-seq(a=v))for(i in combn(J,j,,F))if(all(diff(i)>1)&sum(v[i])>sum(M))M=v[i]
M}

Wypróbuj online!

-1 dzięki @Giuseppe

Wolfram Language (Mathematica) , 70 63 bajtów

MaximalBy[Select[q=Rest@Subsets@#,!FreeQ[q,#~Riffle~_]&],Tr,1]&

Wypróbuj online!

Wyszukiwanie na wysokim poziomie

          Select[q=Rest@Subsets@#,                     ]        (*choose nonempty subsets of the input such that*)
                                  !FreeQ[q,          ]&         (*there exists a subset of the input which matches*)
                                           #~Riffle~_           (*this list, with an item inserted between adjacent elements*)
MaximalBy[                                              ,Tr,1]& (*and return one with the greatest total*)

,1jest wymagane, aby nie zwracać przypadkowo niepoprawnych zestawów (w przeciwnym razie na przykład wejście {1,1,1}spowoduje wynik w postaci {{1,1},{1,1},{1,1}})

Haskell , 300 168 bajtów

import Data.List
h[]=1>2
h(x:y)=fst$foldl(\a c->((fst a)&&(c-snd a>1),c))(1<2,x)y
z=snd.last.sortOn fst.map((,)=<<sum.snd).filter(h.fst).map unzip.subsequences.zip[0..]

Wypróbuj online!

-132 bajtów dzięki wszystkim opiniom @nimi :)

Oryginalny

Niegolfowany (oryginalny)

import Data.List
import Data.Function

f :: [Int] -> [(Int, Int)] -- attach indices for later use
f [] = []
f xs = zip xs [0..length xs]

g :: [[(Int, Int)]] -> [([Int], [Int])] -- rearrange into list of tuples
g [] = []
g (x:xs) = (map fst x, map snd x) : g xs

h :: [Int] -> Bool -- predicate that checks if the indices are at least 2 apart from each other
h [] = False
h (x:xs) = fst $ foldl (\acc curr -> ((fst acc) && (curr - snd acc > 1), curr)) (True, x) xs
j :: [([Int], [Int])] -> [([Int], [Int])] -- remove sets that don't satisfy the condition
j xs = filter (\(elements, indices) -> h indices) xs

k :: [([Int], [Int])] -> [(Int, ([Int], [Int]))] -- calculate some of elements
k xs = map (\(elements, indices) -> (foldl1 (+) elements, (elements, indices))) xs

l :: [(Int, ([Int], [Int]))] -> ([Int], [Int]) -- grab max
l xs = snd $ last $ sortBy (compare `on` fst) xs

z -- put things together
```

Węgiel drzewny , 46 bajtów

≔⟦υ⟧ηＦθ«≔υζ≔Ｅη⁺κ⟦ι⟧υ≔⁺ζηη»≔Φ⁺υηιη≔ＥηΣιζＩ§η⌕ζ⌈ζ

Wypróbuj online! Link jest do pełnej wersji kodu. Wyjaśnienie:

≔⟦υ⟧η

Zmienna ujest predefiniowana z pustą listą. Jest to umieszczone na liście, do której jest przypisany h. Te zmienne działają jak akumulatory. uzawiera listy podrzędne, które zawierają najnowszy element danych wejściowych, qpodczas gdy hzawiera listy podrzędne, które nie (i dlatego nadają się do dołączania następnego elementu danych wejściowych).

Ｆθ«

Pętla nad elementami wejścia.

≔υζ

Zapisz listę podlist, które zawierają poprzedni element.

≔Ｅη⁺κ⟦ι⟧υ

Weź wszystkie podlisty, które nie zawierają poprzedniego elementu, dołącz bieżący element i zapisz wynik jako listę podlist, które zawierają bieżący element. (Nie używam Pushtutaj, ponieważ muszę sklonować listę.)

≔⁺ζηη»

Połącz obie poprzednie podlisty z nową listą podlist, które nie zawierają bieżącego elementu.

≔Φ⁺υηιη

Po raz ostatni połącz listy podrzędne i usuń pierwotną pustą listę (której Charcoal i tak nie może zliczyć).

≔ＥηΣιζ

Oblicz sumy wszystkich podlist.

Ｉ§η⌕ζ⌈ζ

Znajdź indeks największej sumy i wypisz odpowiednią listę podrzędną.

Japt -h , 22 bajty

Êo à k_mÄ øZÃm!gU
fÊñx

Spróbuj

Japt -h , 21 bajtów

Czy kiedykolwiek miałeś jedno z tych wyzwań, w których całkowicie zapominasz, jak grać w golfa ?!

ð¤à fÊk_än ø1îmgUÃñx

Spróbuj

ð¤à fÊk_än ø1îmgUÃñx     :Implicit input of array U
ð                         :Indices of elements that return true when
 ¤                        :  Converted to a base-2 string (to account for 0s)
  à                       :Combinations
    f                     :Filter by
     Ê                    :  Length (to remove the empty combination)
      k_                  :Remove elements that return true
        än                :  Deltas
           ø1             :  Contains 1
             Ã            :End remove
              ®           :Map
               m          :  Map
                gU        :    Index into U
                  Ã       :End map
                   ñ      :Sort by
                    x     :  Sum
                          :Implicit output of last element

Python 2 , 63 70 65 bajtów

f=lambda a:a and max([a[:1],a[:1]+f(a[2:]),f(a[1:])],key=sum)or a

Wypróbuj online!

5 bajtów dzięki ArBo