24
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Should [2,8,2,3,2] be 12 or 17? I presume 17. \$\endgroup\$ – NikoNyrh Jan 4 '18 at 16:02
  • \$\begingroup\$ @NikoNyrh It should be 17. \$\endgroup\$ – Sriotchilism O'Zaic Jan 4 '18 at 16:03
  • \$\begingroup\$ 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. \$\endgroup\$ – Mindwin Jan 4 '18 at 16:35
  • \$\begingroup\$ @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. \$\endgroup\$ – Sriotchilism O'Zaic Jan 4 '18 at 16:39
  • \$\begingroup\$ 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. \$\endgroup\$ – Mindwin Jan 4 '18 at 18:16

22 Answers 22

9
\$\begingroup\$

Haskell, 62 bytes

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.
\$\endgroup\$
8
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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]. \$\endgroup\$ – Neil Jan 4 '18 at 10:53
  • \$\begingroup\$ @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.) \$\endgroup\$ – Arnauld Jan 4 '18 at 11:02
  • \$\begingroup\$ Well, that assumes that they wouldn't misinterpret y-a[i]|(x+=y)<m as (y-a[i]|(x+=y))<m... \$\endgroup\$ – Neil Jan 4 '18 at 13:24
5
\$\begingroup\$

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.
\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

Haskell, 66 bytes

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!

\$\endgroup\$
3
\$\begingroup\$

R, 108 103 90 88 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.

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 54 bytes

Max@SequenceCases[#,{a_,b___,a_}:>2a+b,Overlaps->All]&

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

Clean, 94 90 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!

\$\endgroup\$
  • \$\begingroup\$ I'm afraid this fails for the [1, 1, 80] test case. \$\endgroup\$ – Ørjan Johansen Jan 4 '18 at 1:37
  • \$\begingroup\$ @ØrjanJohansen fixed it \$\endgroup\$ – Οurous Jan 4 '18 at 1:43
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 88 bytes using a lambda function \$\endgroup\$ – Halvard Hummel Jan 4 '18 at 0:34
  • \$\begingroup\$ @HalvardHummel 86 bytes using enumerate. \$\endgroup\$ – Jonathan Frech Jan 4 '18 at 1:55
  • \$\begingroup\$ Outgolfed by Dennis – Honestly, what did you expect? \$\endgroup\$ – Mr. Xcoder Jan 5 '18 at 18:08
  • \$\begingroup\$ @Mr.Xcoder I would have got his solution, but I went to sleep :( \$\endgroup\$ – FlipTack Jan 5 '18 at 18:18
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ 99 bytes, if you like undefined behaviour. \$\endgroup\$ – Jonathan Frech Jan 4 '18 at 1:57
0
\$\begingroup\$

Clojure, 92 bytes

#(apply max(for[i(range(count %))j(range i):when(=(% i)(% j))](apply +(subvec % j(inc i)))))
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Ørjan Johansen Jan 5 '18 at 0:15
0
\$\begingroup\$

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"
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.