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

24

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

Учитывая список целых чисел в качестве входных данных, найдите максимально возможную сумму непрерывного подсписка, который начинается и заканчивается тем же значением. Длина списка должна быть не менее 2. Например, для списка

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

Существуют 2 разных непрерывных списка, начинающихся и заканчивающихся одним и тем же значением

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

Чем больше сумма 9, тем вы выведите 9.

Вы можете предположить, что каждый вход содержит как минимум 1 дубликат.

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

Контрольные примеры

[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 Мастер пшеницы
источник
Должно [2,8,2,3,2]быть 12 или 17? Я предполагаю, 17 лет.
NikoNyrh,
@NikoNyrh Это должно быть 17.
Волшебник Пшеницы
Ура для CC BY / SA. У вас есть право опубликовать производный вопрос другого, даже если он будет помечен как недоумение участниками сообщества. Просто кажется, что вы должны добавить ссылку на страницу ОП, как я получаю из этого поста в блоге. «3. Покажите имена авторов для каждого вопроса и ответа [...] 4. Гиперссылка каждого имени автора непосредственно обратно на страницу их профиля пользователя на исходном сайте» - у меня нет прав видеть удаленные вопросы, поэтому я не Не знаю, кто сделал оригинал.
Mindwin
@Mindwin Спасибо, я добавил ссылку на страницу ОП. Первоначально я пропустил это, потому что решил, что если ОП удалил свою запись, они могли бы избежать ссылки на вопрос.
Пшеничный волшебник
Причина удаления не имеет значения и не прозрачна для обычного пользователя (меня). Но атрибуция имеет вид отказа. Отправляя и соглашаясь с лицензией, они предоставили нам эти права в соответствии с этими условиями. Все, что находится за ее пределами, является исключением. ГДж.
Mindwin

Ответы:

9

Haskell , 62 байта

f принимает список целых чисел и возвращает целое число

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

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

Как это работает

  • tявляется стандартной Data.List.tailsфункцией «получить все суффиксы списка без импорта ».
  • В f l, понимание списка перебирает все непустые суффиксы списка аргументов l, с первым элементом xи остатком m.
  • Для каждого он делает то же самое для всех непустых суффиксов m, выбирая первый элемент yи остаток n.
  • Если xи yравны, понимание списка включает в себя сумму элементов между ними. Этот подсписок такой же, как и x:mс удаленным суффиксом n, поэтому сумма может быть рассчитана как x+sum m-sum n.
Орджан Йохансен
источник
8

JavaScript (ES6), 68 62 байта

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

Контрольные примеры

Показать фрагмент кода

комментарии

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
источник
Я был немного смущен порядком y - a[i]и (x += y) < m- ИМХО код был бы немного понятнее, если бы они обменивались, так как с тех пор он выглядит как простой гольф (x += y) < m || y != a[i].
Нил
@ Нейл, я понимаю твою точку зрения, но это (x+=y)<m|y-a[i]может быть неправильно истолковано (x+=y)<(m|y-a[i]). Я не уверен, что это действительно избавит от двусмысленности. (Отредактировано в любом случае, потому что я предпочитаю эту версию.)
Арно
Ну, это предполагает, что они не будут неверно истолкованы y-a[i]|(x+=y)<mкак (y-a[i]|(x+=y))<m...
Нил
5

Желе , 12 байт

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

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

Как это работает

ĠŒ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.
Деннис
источник
5

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

▲mΣfΓ~€;ṫQ

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

объяснение

▲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
источник
3

R , 108 103 90 88 83 байта

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

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

combnзабастовки снова! Генерирует как минимум все подсписки длины 2, устанавливает сумму подсписка -Infравной, если первый и последний не равны, и принимает максимум всех сумм.

Он "if"выдаст кучу предупреждений, но они безопасно игнорируются - это, вероятно, лучший трюк в гольфе, он rev(p)-pравен нулю в первом элементе iff p[1]==tail(p,1)и "if"использует первый элемент своего состояния с предупреждением.

Giuseppe
источник
2

Желе , 13 , 12 байт

=ṚṖḢ
ẆÇÐfS€Ṁ

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

Один байт спас Мистер Xcoder, который в настоящее время конкурирует со мной. : D

Объяснение:

        # 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
источник
1

Pyth, 15 байт

eSsMf&qhTeTtT.:

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

объяснение

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 байтов

ŒʒćsθQ}OZ

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

объяснение

Π         # 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
источник
1

Чистый , 94 90 86 байт

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

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

Οurous
источник
Я боюсь, что это не удастся для [1, 1, 80]теста.
Орджан Йохансен
@ ØrjanJohansen исправил это
Οurous
1

Python 2 , 86 байт

Превосходящий Деннис

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

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

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

FlipTack
источник
88 байтов с использованием лямбда-функции
Halvard Hummel
@HalvardHummel 86 байт, используя enumerate.
Джонатан Фрех
Превзойденный Деннисом - Честно говоря, что вы ожидали?
г-н Xcoder
@ Mr.Xcoder Я бы получил его решение, но я пошел спать :(
FlipTack
1

Желе , 11 байт

Использует некоторые функции, которые ставят после проблемы.

Ẇµ.ịEȧḊµƇ§Ṁ

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

Как это работает?

Ẇµ.ịEȧḊµƇ§Ṁ || Полная программа. Принимает вход от CLA, выводит на STDOUT.
Ẇ || Подсписки.
 µ µƇ || Фильтр-держи тех
    ȧḊ || ... которые имеют длину не менее 2 и ...
 .ị || ... Элементы на полу (0,5) и потолке (0,5) (модульные, 1-индексированные) ...
    E || ... Равны.
         § || Сумма каждого.
          Ṁ || Максимум.

-1 с помощью Кэрда .

Мистер Xcoder
источник
0

Пакет, 179 байт

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

Принимает ввод как параметры командной строки.

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

Clojure, 92 байта

#(apply max(for[i(range(count %))j(range i):when(=(% i)(% j))](apply +(subvec % j(inc i)))))
NikoNyrh
источник
0

Java 8, 129 байсов

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

Для каждого целого числа Xв списке функция находит сумму самого большого подсписка с начала и конца X. Затем он находит максимальную сумму, указанную в OP.

Марио Исхак
источник
Я не проверял это, но мне кажется, что оно может не сработать в [2,8,2,-3,2]тестовом случае, и, возможно, [1,1,80]тоже.
Орджан Йохансен
0

Perl 61 59 байт

Включает +3для -p:

max_ident_run.pl:

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

Беги как:

max_ident_run.pl <<< "1 2 -2 4 1 4 1"
Тон Хоспел
источник