# Maximum run between identical elements

This is a overhaul of this now deleted question by ar kang. If the OP of that question would like to reclaim this question or has a problem with me posting this I'd be happy to accommodate

Given a list of integers as input find the maximum possible sum of a continuous sublist that starts and ends with the same value. The sublists must be of length at least 2. For example for the list

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


There are 2 different continuous sublists start and end with the same value

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


The bigger sum is 9 so you output 9.

You may assume every input contains at least 1 duplicate.

This is so answers will be scored in bytes with fewer bytes being better.

## Test cases

[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

• Should [2,8,2,3,2] be 12 or 17? I presume 17. Commented Jan 4, 2018 at 16:02
• @NikoNyrh It should be 17. Commented Jan 4, 2018 at 16:03
• Hooray for CC BY/SA. You have the right to post a derivative question of another one, even if it would be later flagged dupe by community members. It just seems you should add a link to the OP's page as I get from this blog post. "3. Show the author names for every question and answer [...] 4. Hyperlink each author name directly back to their user profile page on the source site" - I don't have privileges to see deleted questions, so I don't know who made the original one. Commented Jan 4, 2018 at 16:35
• @Mindwin Thanks, I've added a link to the OP's page. I left it out originally because I figured if the OP deleted their post they might want to avoid being linked to the question. Commented Jan 4, 2018 at 16:39
• The reason for deletion is irrelevant and not transparent to the common user (me). But attribution is of the opt-out kind. By submitting and agreeing to the license they granted us those rights under those conditions. Anything outside it is an exception. GJ. Commented Jan 4, 2018 at 18:16

f takes a list of integers and returns an integer.

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


Try it online!

# How it works

• t is the standard "get all suffixes of a list without importing Data.List.tails" function.
• In f l, the list comprehension iterates through all the non-empty suffixes of the argument list l, with first element x and remainder m.
• For each, it does the same for all nonempty suffixes of m, selecting first element y and remainder n.
• If x and y are equal, the list comprehension includes the sum of the elements between them. This sublist is the same as x:m with its suffix n stripped off, so the sum can be calculated as x+sum m-sum n.

# 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


### Test cases

let f =

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

console.log(f([1,2,-2,4,1,4] )) // -> 9
console.log(f([1,2,1,2]      )) // -> 5
console.log(f([-1,-2,-1,-2]  )) // -> -4
console.log(f([1,1,1,8,-1,8] )) // -> 15
console.log(f([1,1,1,-1,6,-1])) // -> 4
console.log(f([2,8,2,-3,2]   )) // -> 12
console.log(f([1,1,80]       )) // -> 2

### Commented

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

• I was slightly confused by the ordering of y - a[i] and (x += y) < m - IMHO the code would be slightly clearer with them exchanged, since then it looks like a simple golf from (x += y) < m || y != a[i].
– Neil
Commented Jan 4, 2018 at 10:53
• @Neil I see your point but (x+=y)<m|y-a[i] could be misinterpreted as (x+=y)<(m|y-a[i]) just as well. I'm not sure it would really strip away the ambiguity. (Edited anyway because I tend to prefer this version.) Commented Jan 4, 2018 at 11:02
• Well, that assumes that they wouldn't misinterpret y-a[i]|(x+=y)<m as (y-a[i]|(x+=y))<m...
– Neil
Commented Jan 4, 2018 at 13:24

# Jelly, 12 bytes

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


Try it online!

### How it works

ĠŒ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.


# Husk, 10 bytes

▲mΣfΓ~€;ṫQ


Try it online!

## Explanation

▲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


maximum.f
f(x:y)=[sum$x:take a y|(a,b)<-zip[1..]y,b==x]++f y f x=x  Try it online! # R, 1081039088 83 bytes function(l)max(combn(seq(l),2,function(x)"if"(rev(p<-l[x[1]:x[2]])-p,-Inf,sum(p))))  Try it online! combn strikes again! Generates all sublists of length at least 2, sets the sublist sum to -Inf if the first and last are not equal, and takes the max of all the sums. The "if" will raise a bunch of warnings but they are safely ignorable -- that's probably the best golfing trick here, rev(p)-p is zero in the first element iff p[1]==tail(p,1), and "if" uses the first element of its condition with a warning. # Python 3, 81 bytes lambda x,e=enumerate:max(sum(x[i:j+1])for i,a in e(x)for j,b in e(x)if(a==b)*j>i)  Try it online! # Python, 62 bytes f=lambda l:l and max(f(l[1:]),[sum(l)]*(l.pop()in l[:1]),f(l))  Try it online! Outputs a singleton list. # Jelly, 13, 12 bytes =ṚṖḢ ẆÇÐfS€Ṁ  Try it online! One byte saved by Mr. Xcoder, who is currently competing with me. :D Explanation:  # 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  ## Wolfram Language (Mathematica), 54 bytes Max@SequenceCases[#,{a_,b___,a_}:>2a+b,Overlaps->All]&  Try it online! # Pyth, 15 bytes eSsMf&qhTeTtT.:  Try it online ### Explanation 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.  # 05AB1E, 9 bytes ŒʒćsθQ}OZ  Try it online! Explanation Œ # 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  # Clean, 9490 86 bytes import StdEnv,StdLib @l=last(sort[sum(l%(i,j))\\e<-l&i<-[0..],j<-elemIndices e l|j>i])  Try it online! • I'm afraid this fails for the [1, 1, 80] test case. Commented Jan 4, 2018 at 1:37 • @ØrjanJohansen fixed it Commented Jan 4, 2018 at 1:43 # Python 2, 86 bytes 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])  Try it online! Generates all sublists larger than length 2, where the first element is equal to the last, then maps each to its sum and selects the largest value. • 88 bytes using a lambda function Commented Jan 4, 2018 at 0:34 • @HalvardHummel 86 bytes using enumerate. Commented Jan 4, 2018 at 1:55 • Outgolfed by Dennis – Honestly, what did you expect? Commented Jan 5, 2018 at 18:08 • @Mr.Xcoder I would have got his solution, but I went to sleep :( Commented Jan 5, 2018 at 18:18 # Ruby, 64 bytes ->l{w,*r=0;(z=l.index w)&&r<<w+l[z..-1].sum while w=l.pop;r.max}  Try it online! # Julia 0.6, 70 bytes a->maximum(sum(a[i:k]) for b=[findin(a,x) for x=a] for i=b,k=b if k>i)  Try it online! # Jelly, 11 bytes Uses some features that post-date the challenge. Ẇµ.ịEȧḊµƇ§Ṁ  Try it online! ### How it works? Ẇµ.ịEȧḊµƇ§Ṁ || Full program. Takes input from CLA, outputs to STDOUT. Ẇ || Sublists. µ µƇ || Filter-Keep those ȧḊ || ... Which have length at least 2 and ... .ị || ... The elements at floor(0.5) and ceil(0.5) (modular, 1-indexed) ... E || ... Are equal. § || Sum each. Ṁ || Maximum.  -1 with help from caird. ## Batch, 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%  Takes input as command-line parameters. # 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;}  Try it 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;}  Try it online! • 99 bytes, if you like undefined behaviour. Commented Jan 4, 2018 at 1:57 ## Clojure, 92 bytes #(apply max(for[i(range(count %))j(range i):when(=(% i)(% j))](apply +(subvec % j(inc i)))))  ## 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()  For each integer X in the list, the function finds the sum of the largest sublist with start and end X. Then, it finds the maximum sum as the OP specifies. • I haven't tested it, but that looks to me like it might fail on the [2,8,2,-3,2] test case, and possibly [1,1,80] too. Commented Jan 5, 2018 at 0:15 # Perl, 61 59 bytes Includes +3 for -p: max_ident_run.pl: #!/usr/bin/perl -p s:\S+:$%=$&;($%+=$_)<($\//$%)||$_-$&or$\=$%for<$' >:eg}{


Run as:

max_ident_run.pl <<< "1 2 -2 4 1 4 1"