22
\$\begingroup\$

Input:

A non-empty sequence of integers greater than zero, the length of which is greater than 1.

Output:

The largest product of all elements of the longest subsequence between the minimum and maximum elements of sequence including themselves.

Note:

Because the minimum and maximum elements can be repeated, then to a definite answer necessary to find the longest possible subsequence, at one end of which is a minimum and at the other end maximum elements of the sequence. If there is multiple longest subsequences then choose subsequence with largest product.

Examples:

1st example:

Input: [5, 7, 3, 2, 1, 2, 2, 7, 5]

Output: 42

Explanation: min == 1, max == 7. There is 2 possible subsequences with min and max on ends: [1, 2, 2, 7] and [7, 3, 2, 1]. Their length is equal, so comparing products: 7*3*2*1 == 42 and 1*2*2*7 == 28. Because 42 >= 28, answer: 42.

2nd example:

Input: [1, 2, 2, 2, 4, 3, 3, 1]

Output: 32

Explanation: min == 1, max == 4. 2 subsequences: [1, 2, 2, 2, 4] and [4, 3, 3, 1]. Length of [1, 2, 2, 2, 4] is greater than length of [4, 3, 3, 1]. product: 1*2*2*2*4 == 32 => answer is 32.

3d example:

Input: [1, 2, 3, 4, 3, 3, 1]

Output: 36

Short explanation: min == 1, max == 4. 2 subsequences: [1, 2, 3, 4] and [4, 3, 3, 1]. 1*2*3*4 == 24, 4*3*3*1 == 36, 36 >= 24 => answer is 36.

4th example:

Input: [2, 2, 2]

Output: 8

Explanation: min == 2, max == 2. 2 different subsequences: [2, 2] and [2, 2, 2]. Length of [2, 2, 2] is greater than length of [2, 2]. product: 2*2*2 == 8 => answer is 8.

More (random) examples:

>>>[7, 2, 3, 6, 8, 6, 2, 5, 4, 3]
288
>>>[3, 3, 8, 9, 1, 7, 7, 2, 2, 4]
9
>>>[3, 2, 6, 5, 4, 1, 8, 8, 7, 9]
4032
>>>[7, 4, 2, 8, 8, 3, 9, 9, 5, 6]
31104

Check your solution:

Here is Python 3 lambda (788 bytes), which satisfies the requirement of the task:

lambda O: __import__('functools').reduce(__import__('operator').mul,O[[[slice(O.index(max(O)),len(O)-1-O[::-1].index(min(O))+1),slice(O.index(min(O)),(len(O)-1-O[::-1].index(max(O)))+1)][__import__('functools').reduce(__import__('operator').mul,O[O.index(min(O)):(len(O)-1-O[::-1].index(max(O)))+1],1)>=__import__('functools').reduce(__import__('operator').mul,O[O.index(max(O)):len(O)-1-O[::-1].index(min(O))+1],1)],slice(O.index(min(O)),(len(O)-1-O[::-1].index(max(O)))+1),slice(O.index(max(O)),len(O)-1-O[::-1].index(min(O))+1)][(len(range(O.index(min(O)),(len(O)-1-O[::-1].index(max(O)))+1))>len(range(O.index(max(O)),len(O)-1-O[::-1].index(min(O))+1)))-(len(range(O.index(min(O)),(len(O)-1-O[::-1].index(max(O)))+1))<len(range(O.index(max(O)),len(O)-1-O[::-1].index(min(O))+1)))]],1)

Winner:

Shortest solution will win. All programming languages accepted.

P.S.: I will be happy to the explanations of your solutions

\$\endgroup\$
5
\$\begingroup\$

Jelly, 14 bytes

.ịạ/;L;P
ẆÇ€ṀṪ

Try it online!

How it works

ẆÇ€ṀṪ     Main link. Argument: A (array)

Ẇ         Window; generate all substrings of A.
 ǀ       Map the helper link over the substrings.
   Ṁ      Take the maximum.
    Ṫ     Tail; select the last element.


.ịạ/;L;P  Helper link. Argument: S (array / substring)

.ị        At-index 0.5; select the last and first element of S.
  ạ/      Reduce by absolute difference.
    ;L    Append the length of S.
      ;P  Append the product of S.
|improve this answer|||||
\$\endgroup\$
5
\$\begingroup\$

Jelly, 15 bytes

NMpMr/€LÐṀịµP€Ṁ

TryItOnline!

How?

NMpMr/€LÐṀịµP€Ṁ - Main link: list of integers, L
           µ    - links to the left as a monadic chain with argument L
N               - negate elements of L
 M              - indexes of maximal elements (i.e. indexes of minimal elements of L)
   M            - indexes of maximal elements of L
  p             - Cartesian product of the min and max indexes
     /€         - reduce each list (all of which are pairs) with the dyad:
    r           -     range(a,b)  (note if a>b this is [a,a-1,...,b])
        ÐṀ      - filter keeping those with maximal
       L        -     length
          ị     - index into L (vectorises)   (get the values)
            P€  - product of a list for €ach
              Ṁ - maximum
|improve this answer|||||
\$\endgroup\$
5
\$\begingroup\$

Perl 6, 108 bytes

{max ([*] $_ for .[.grep(+.max(+*)) with (for .min,.max,.max,.min {.first($^a,:k).. .first($^b,:k,:end)})])}
|improve this answer|||||
\$\endgroup\$
3
\$\begingroup\$

R, 146 bytes

z=apply(expand.grid(which(max(x<-scan())==x),which(min(x)==x)),1,function(y)c(prod(x[y[1]:y[2]]),abs(diff(y))));max(z[1,which(z[2,]==max(z[2,]))])

Tricky challenge because of the length requirement. Also annoying because the would-be useful builtin which.max only returns the index of the first maximum it encounters, forcing me to use which(max(x)==x) instead... 3 times. Ohwell...

Readable:

x <- scan()

maxs <- which(max(x)==x)
mins <- which(min(x)==x)
q <- expand.grid(maxs,mins)
z <- apply(q,1,function(y){
  c(prod(x[y[1]:y[2]]), abs(diff(y)))
  })

max(z[1, which(z[2, ]==max(z[2, ]))])
|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

PHP, 189 173 166 bytes

<?foreach($a=$_GET[a]as$p=>$b)foreach($a as$q=>$c)$b>min($a)|$c<max($a)?:$r[$d=abs($p-$q)+1]=array_product(array_slice($a,min($p,$q),$d));ksort($r);echo max(end($r));

similarly lazy but 33 bytes shorter (had to add 10 bytes to turn the snippet into a program):

  1. Loop $p/$b and $q/$c through the array; if $b==min and $c==max,
    add product of the sub-sequence to $r[sub-sequence length]
  2. Sort $r by keys.
  3. Print the max value of the last element.

Call in browser with array as GET parameter a.
Example: script.php?a[]=5&a[]=7&a[]=3&a[]=2&a[]=1&a[]=2&a[]=2&a[]=7&a[]=5

|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

Mathematica, 122 bytes

(g=#;Sort[{#.{-1,1},Times@@Take[g,#]}&/@Sort/@Join@@Outer[List,Sequence@@(Union@@Position[g,#@g]&/@{Max,Min})]][[-1,-1]])&

Surprised how long this turned out to be. First generates the Cartesian product of the appearances of the minima and maxima (as per Jonathan Allan's Jelly answer), then computes the lengths of those runs and their products, and selects the appropriate one by taking the last element of the sorted results.

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

JavaScript, 187 bytes

f=
(l,M=Math,a=M.min(...l),z=M.max(...l),r=(m,n)=>[eval(l.slice(b=l.indexOf(m),c=l.lastIndexOf(n)+1).join`*`),M.abs(b-c)])=>(u=r(a,z),v=r(z,a),u[1]>v[1]?u[0]:v[1]>u[1]?v[0]:M.max(v[0],u[0]))


console.log([
  [5, 7, 3, 2, 1, 2, 2, 7, 5],
  [1, 2, 2, 2, 4, 3, 3, 1],
  [1, 2, 3, 4, 3, 3, 1],
  [2, 2, 2],
  [7, 2, 3, 6, 8, 6, 2, 5, 4, 3],
  [3, 3, 8, 9, 1, 7, 7, 2, 2, 4],
  [3, 2, 6, 5, 4, 1, 8, 8, 7, 9],
  [7, 4, 2, 8, 8, 3, 9, 9, 5, 6]
].map(a=>`[${a}] => ${f(a)}`).join`
`)

|improve this answer|||||
\$\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.