Максимально суммированные подпоследовательности с несмежными элементами

23

Введение:

Вдохновленные этими двумя SO-вопросами (без сомнения, из одного и того же класса): выведите элементы в подмассиве максимальной суммы без смежных элементов java и максимальной суммы несмежных элементов массива, которые будут напечатаны .

Вызов:

Учитывая список целых чисел, выведите подпоследовательность, состоящую из несмежных элементов, которые имеют наибольшую сумму. Вот несколько примеров:

  • [1,2,3,-1,-3,2,5]приведет к [1,3,5](с суммой 9) на основе индексов 0 [0,2,6].
  • [4,5,4,3]приведет к либо [4,4](с суммой 8) в индексах на основе 0, [0,2]либо [5,3](также с суммой 8) в индексах на основе 0 [1,3].
  • [5,5,10,100,10,5]приведет к [5,100,5](с суммой 110) либо на основе индексов 0 [0,3,5]или [1,3,5].

Что наиболее важно в приведенных выше примерах, индексы, содержащие элементы, по крайней мере, 2 расположены друг от друга. Если мы посмотрим на пример [5,5,10,100,10,5]более подробно: у нас есть следующая потенциальная подпоследовательность, содержащая несмежные элементы; с их индексами ниже; с их суммами ниже этого:

[[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

Поскольку максимальные суммы равны 110, мы выводим [5,100,5]результат.

Правила соревнований:

  • Вам разрешено выводить пары ключ-значение индекса + значение. Таким образом, вместо [5,100,5]вы можете выводить [[0,5],[3,100],[5,5]]или [[1,5],[3,100],[5,5]]как результат (или [[1,5],[4,100],[6,5]]/ [[2,5],[4,100],[6,5]]когда используется индексация на основе 1 вместо 0 на основе).
    • Если вы используете пары ключ-значение, они также могут быть в обратном или случайном порядке, поскольку ясно, какие значения подразумеваются из-за парного индекса.
    • Вывод только индексов без значений не допускается. Он должен либо выводить значения, либо значения / индексы в виде пар ключ-значение (или двух разделенных списков для «ключей» и «значений» одинакового размера, если пары ключ-значение невозможны на выбранном вами языке).
  • Вам разрешено выводить все возможные подпоследовательности с максимальной суммой вместо одной.
  • Как видно из примеров, список ввода может содержать как отрицательные, так и дублированные значения. Можно предположить, что входные целые числа находятся в диапазоне [−999,999] .
  • Выходной список не может быть пустым и всегда должен содержать хотя бы один элемент (если список будет содержать только отрицательные значения, то в качестве результата будет выведен список, содержащий единственное наименьшее отрицательное значение - см. Последние два теста).
  • Если есть один возможный вывод, но для нескольких разных индексов, разрешается выводить оба из них, даже если они выглядят дубликатами. (т.е. приведенный выше пример может выводить [[5,100,5],[5,100,5]]обе возможные комбинации индексов).

Тестовые случаи:

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
code-golf number array-manipulation integer Кевин Круйссен
источник
Если существует более одного идентичного набора (но из разных индексов), можно ли перечислить их все? например, [5,100,5]дважды для вашего третьего примера.
Ник Кеннеди
1
powersetэто набор подмножеств, не так ли? но похоже, что вы возвращаете набор подпоследовательностей? [4,5,4,3] привело бы к [4,4], где [4,4] явно не является набором.
Просроченные данные
1
@Arnauld Да, если значения являются парами ключ-значение с их индексом, ясно, какие индексированные значения подразумеваются во входных данных, поэтому они могут быть в любом порядке. Также отредактирую это в описании вызова.
Кевин Круйссен
2
Просто чтобы быть уверенным: вывод индексов не вариант, не так ли?
лохматый
1
Классический термин «подпоследовательность» . Однако это та же проблема, что и люди, думающие о смежных подпоследовательностях. Я бы сказал «подмножество», если бы мы на самом деле работали с наборами здесь, но это определенно последовательности - порядок вопросов и дубликаты разрешены.
user2357112 поддерживает Monica

Ответы:

6

Шелуха , 11 байт

►Σ†!¹mü≈tṖŀ

Попробуйте онлайн!

объяснение

►Σ†!¹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]
Zgarb
источник
6

Haskell , 60 байт

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

Попробуйте онлайн!

Вспомогательная функция %рекурсивно разветвляется при выборе: включить первый элемент и отбросить второй или пропустить первый элемент. Он принимает максимум всех результатов, которые являются кортежами, первый элемент которых является суммой, а второй элемент - соответствующим списком, который извлекается для вывода.

Чтобы справиться с правилом, согласно которому пустой список запрещен, даже если он будет иметь наименьшую хитрость, мы пишем симпатичный трюк, sum r<$rа не. sum rЭто создает список, все элементы sum rкоторого и длина которого равна r. Таким образом, когда мы выбираем максимум, мы отдаем приоритет любому списку над пустым r, но в противном случае сравнения зависят от первого элемента, который есть sum r.

XNOR
источник
6

R , 136 125 байт

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

Попробуйте онлайн!

-6 байт благодаря digEmAll , который, кстати, тоже превзошел меня .

Возвращает самую короткую подпоследовательность как a list, разрывая связи по лексикографически сначала по индексам.

Грубая сила генерирует все подпоследовательности индекса, затем Filters для несмежных, т. Е. Где all(diff(x)>1). Тогда подмножества [в lиспользовании этих индексов, выбирая [[первую , где сумма является макс ( which.max).

Я уверен, что это первый ответ R, который я когда-либо писал, который использует Filter! грустно, Filterнечестно, не удивительно, что я никогда не использовал его ...

Giuseppe
источник
130
digEmAll
@digEm Всем спасибо!
Джузеппе
5

05AB1E , 14 байтов

Сохранено 1 байт благодаря Кевину Круйссену

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

Попробуйте онлайн! или как тестовый набор

объяснение

ā<               # 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
Emigna
источник
Возможно, вы не будете счастливы, но это все еще на 4 байта короче, чем мое первоначальное решение. ;) И вы можете играть в гольф еще 1 меняется ¤ªна Ć.
Кевин Круйссен
@KevinCruijssen: О да! По какой-то причине я убедил себя, что мне нужен повторный элемент в конце. Благодарность!
Эминья
5

Brachylog (v2), 14 байт

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

Попробуйте онлайн!

Подчинение функции; ввод слева, вывод справа, как обычно. Очень медленно; список из пяти элементов, вероятно, является максимальным для тестирования на 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

Результаты, которые мы получаем из префиксов, не являются неверными, но также не интересны; все возможные результаты генерируются с помощью суффикса (который, возможно, является самим списком, но не может быть пустым), но «суффикс» в Brachylog более многословен, чем «префикс или суффикс», поэтому я выбрал версию, которая более краткая (и менее эффективный но все же правильный). Основная идея состоит в том, что для каждого элемента, который мы хотим в выходном списке, разделение на смежные подсписки должно поместить этот элемент и элемент в один и тот же подсписок (потому что элемент является вторымэлемент подсписка), поэтому два последовательных элемента не могут появиться в результате. С другой стороны, совершенно очевидно, что в результате может появиться любой список без двух последовательных элементов. Поэтому, когда у нас есть все возможные списки кандидатов, мы можем просто взять суммы всех из них и посмотреть, какой из них самый большой.

ais523
источник
3

JavaScript (ES6),  138 132 130 129  126 байтов

Вывод пар ключ-значение.

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

Попробуйте онлайн!

Шаг 1

[vaLUе,яNdеИкс] .

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

Шаг 2

Затем мы ищем максимальную сумму мсреди этих наборов отбрасывают наборы, по меньшей мере, с двумя смежными элементами. Лучший набор хранится вр,

.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[]
Arnauld
источник
3

Haskell, 81 80 байт

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

Попробуйте онлайн!

fсоздает все допустимые подпоследовательности, пропуская следующий элемент ( f(b:c)) или используя его и пропуская next ( map(a:)(f c)), и рекурсивно работает с остальными. Для результата создайте все подпоследовательности ( f), удалите пустую подпоследовательность (которая появляется первой в списке:) tail, сделайте пары (<sum>,<subsequence>)( map((,)=<<sum)), найдите максимум (пары сравниваются в лексикографическом порядке) -> maximum) и отбросьте сумму ( snd).

Редактировать: -1 байт благодаря @Lynn.

Ними
источник
1
map(:[])aна байт короче (pure<$>a)^^
Линн
3

T-SQL, 122 119 118 байт

Ввод является табличной переменной.

Этот запрос выбирает все элементы из табличной переменной, комбинируя их со всеми несмежными элементами с более высокими значениями позиции и показывает текст, сгенерированный для наибольшей суммы этих значений.

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

Попробуйте онлайн ungolfed

t-clausen.dk
источник
2

Pyth, 19 байт

esDm@LQdtf!q#1.+TyU

Попробуйте онлайн здесь или проверьте все тестовые примеры сразу здесь .

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
Sok
источник
2

Gaia , 24 байта

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

Попробуйте онлайн!

Тьфу, E‡делают некоторые странные вещи ... в соответствии с документацией, он должен сделать что - то вроде «заданной длиной iмножества списков Xи длиной jнабора индексов Y, возвращения X[i][Y[j]]», но вместо этого возвращается , [X[i][Y[j]] X[i][Y[-j]]где отрицательное индексирование представляет дополнение, так что мы должны сделать , ev2%чтобы извлекать только те, которые мы хотим.

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
Giuseppe
источник
Из любопытства, почему у выхода есть два трейлинга ]]вместо одного?
Кевин Круйссен
@KevinCruijssen Еще одна забавная причуда переводчика; все списки распечатываются таким образом, поэтому [[1] [2]]печатается, [[1]] [2]]]]что затрудняет чтение / отладку вывода списка.
Джузеппе
Я думаю, что это из-за выражения re.sub(" ?$","]",result)в интерпретаторе, которое должно быть, re.sub(" +$","]",result)но мой питон очень плохой.
Джузеппе
2

Wolfram Language (Mathematica) , 70 63 байта

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

Попробуйте онлайн!

Поиск высокого уровня

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

,1требуется, чтобы непреднамеренно не возвращать недопустимые наборы (в противном случае, например, ввод в {1,1,1}результате приведет к выводу {{1,1},{1,1},{1,1}})

attinat
источник
1

Haskell , 300 168 байт

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

Попробуйте онлайн!

-132 байта благодаря всем отзывам от @nimi :)

оригинал

Ungolfed (оригинал)

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
```
ошибки
источник
1
Несколько советов: переверните элемент и его индекс в парах, возвращаемых f:, f x=zip[0..length x]xтак fстановится f=zip[0..]. gэто просто g=map unzip. Функция для фильтрации с помощью jis h.fst(<- перевернутые пары!). j=filter(h.fst), foldl1+От kэто sumи с pointfree пары решений k=map((,)=<<sum.snd). sortBy(...)может быть заменен на sortOn fst: l=snd.last.sortOn fst. Наконец, поскольку вы используете все функции только один раз, вы можете встроить их в одно выражение без точек:z=snd.last.sortOn fst.map((,)=<<sum.snd).filter(h.fst).map unzip.subsequences.zip[0..]
nimi
.... Попробуй онлайн! ,
Ними
о, и не нужно Data.Functionбольше импортировать .
Ними
Здорово, спасибо за отзыв :)
баги
Далее h: мы ищем несмежные элементы, т.е. разница смежных индексов должна быть >1. zipWith(-)=<<tailстроит такой список различий, но не выполняется для пустого списка, так что нам нужно дополнительно tailна , subsequencesчтобы избавиться от него. Снова в строке. Попробуйте онлайн!
Ними
1

Древесный уголь , 46 байт

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

Попробуйте онлайн!Ссылка на подробную версию кода. Объяснение:

≔⟦υ⟧η

Переменная uпредопределена с пустым списком. Это помещено в список, который назначен h. Эти переменные действуют как аккумуляторы. uсодержит подсписки, которые включают самый последний элемент ввода, в qто время какh содержит подсписки, которые этого не делают (и, следовательно, подходят для добавления следующего элемента ввода).

Ｆθ«

Цикл по элементам ввода.

≔υζ

Сохраните список подсписков, которые содержат предыдущий элемент.

≔Ｅη⁺κ⟦ι⟧υ

Возьмите все подсписки, которые не содержат предыдущий элемент, добавьте текущий элемент и сохраните результат как список подсписков, которые содержат текущий элемент. (Я не использую Pushздесь, поскольку мне нужно клонировать список.)

≔⁺ζηη»

Объединить оба предыдущих подсписка в новый список подсписков, которые не содержат текущий элемент.

≔Φ⁺υηιη

Объедините подсписки в последний раз и удалите исходный пустой список (который в любом случае уголь не может суммировать).

≔ＥηΣιζ

Вычислите суммы всех подсписков.

Ｉ§η⌕ζ⌈ζ

Найдите индекс наибольшей суммы и выведите соответствующий подсписок.

Нил
источник
1

Japt -h , 21 байт

У вас когда-нибудь возникали проблемы, когда вы совершенно забыли, как играть в гольф ?!

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

Попытайся

ð¤à 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
мохнатый
источник