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\$
5
  • \$\begingroup\$ Should [2,8,2,3,2] be 12 or 17? I presume 17. \$\endgroup\$
    – NikoNyrh
    Jan 4, 2018 at 16:02
  • \$\begingroup\$ @NikoNyrh It should be 17. \$\endgroup\$
    – Wheat Wizard
    Jan 4, 2018 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\$ Jan 4, 2018 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\$
    – Wheat Wizard
    Jan 4, 2018 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\$ Jan 4, 2018 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\$
0
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\$
3
  • \$\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, 2018 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, 2018 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, 2018 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\$
0
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\$
2
  • \$\begingroup\$ I'm afraid this fails for the [1, 1, 80] test case. \$\endgroup\$ Jan 4, 2018 at 1:37
  • \$\begingroup\$ @ØrjanJohansen fixed it \$\endgroup\$
    – Οurous
    Jan 4, 2018 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\$
4
  • \$\begingroup\$ 88 bytes using a lambda function \$\endgroup\$ Jan 4, 2018 at 0:34
  • \$\begingroup\$ @HalvardHummel 86 bytes using enumerate. \$\endgroup\$ Jan 4, 2018 at 1:55
  • \$\begingroup\$ Outgolfed by Dennis – Honestly, what did you expect? \$\endgroup\$
    – Mr. Xcoder
    Jan 5, 2018 at 18:08
  • \$\begingroup\$ @Mr.Xcoder I would have got his solution, but I went to sleep :( \$\endgroup\$
    – FlipTack
    Jan 5, 2018 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
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\$
1
  • \$\begingroup\$ 99 bytes, if you like undefined behaviour. \$\endgroup\$ Jan 4, 2018 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\$
1
  • \$\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\$ Jan 5, 2018 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 and acknowledge you have read our privacy policy.

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