Sous-tableau maximum

21

Définissez le "sous-tableau maximum" d'un tableau donné comme "un sous-tableau (consécutif) qui a la plus grande somme". Notez qu'il n'y a aucune exigence "non nulle". Sortez cette somme.

Donnez une description de votre code si possible.

Exemple d'entrée 1:

1 2 3 -4 -5 6 7 -8 9 10 -11 -12 -13 14

Exemple de sortie 1: 24

Description 1:
La plus grande somme est obtenue en découpant 6 7 -8 9 10et en résumant.

Exemple d'entrée 2: -1 -2 -3
Exemple de sortie 2: 0
Description 2: C'est simple :) Un sous-tableau vide est le "plus grand".

Exigence:

  • Ne lisez rien sauf stdin, et la sortie devrait aller à stdout.
  • Des restrictions d' échappatoires standard s'appliquent.

Classement: Le programme le plus court remporte ce .

iBug
la source
5
Écrivez un programme aussi court que possible. Je recommanderais de supprimer cette exigence car elle nous oblige à vérifier tous les programmes possibles dans notre langue et à nous assurer que nous utilisons le plus court.
Okx
L'exigence 2 n'est pas claire non plus. Cela signifie-t-il les bibliothèques? Bibliothèques personnalisées? Externaliser le programme? Ce dernier est déjà interdit par les failles standard.
Leaky Nun
14
Ne lisez rien sauf stdin et n'écrivez nulle part sauf stdout. - Pourquoi?
M. Xcoder du
2
Très similaire , peut-être un dupe. Également très similaire .
xnor

Réponses:

10

Husk , 6 4 octets

▲ṁ∫ṫ

Essayez-le en ligne!

      -- implicit input (list) xs  - eg. [-1,2,3]
   ṫ  -- get all tails of xs       -     [[-1,2,3],[2,3],[3],[]]
 ṁ∫   -- map & concat cumsum       -     [0,-1,1,4,0,2,5,0,3,0]
▲     -- get maximum               -     5
ბიმო
la source
4

Pyth , 8 octets

eS+0sM.:

Essayez-le en ligne!


Comment?

eS + 0sM.: Q - Q est implicite, ce qui signifie entrée. Disons que c'est [-1, -2, -3].

      .: - Toutes les sous-listes contiguës non vides. Nous avons [[-1], [-2], [-3], [-1, -2], [-2, -3], [-1, -2, -3]].
    sM - Obtenez la somme de chaque sous-liste. [-1, -2, -3, -3, -5, -6]
  +0 - Ajoutez un 0 à la liste de somme. [0, -1, -2, -3, -3, -5, -6]
eS - Élément maximum. S nous donne [-6, -5, -3, -3, -2, -1, 0], tandis que e renvoie 0, le dernier élément.
M. Xcoder
la source
4

05AB1E , 4 octets

Ό0M

Essayez-le en ligne!

-1 merci à Adnan .

Erik le Outgolfer
la source
Même astuce qu'avec la réponse d'Okx: ÎŒOMdevrait fonctionner pendant 4 octets.
Adnan
@Adnan Merci, je pensais qu'il n'y avait qu'un "1 et entrée" intégré ... attendez ... n'est-ce pas? Ne devraient-ils pas être concaténés ou quelque chose?
Erik the Outgolfer du
Non, Mrecherche le plus grand nombre dans la version aplatie de la pile.
Adnan
@Adnan ok ... c'est une nouvelle pour moi lol
Erik the Outgolfer
3

C ++, 197 195 187 octets

-10 octets grâce à Zacharý

#include<vector>
#include<numeric>
int f(std::vector<int>v){int i=0,j,t,r=0;for(;i<v.size();++i)for(j=i;j<v.size();++j){t=std::accumulate(v.begin()+i,v.begin()+j,0);if(t>r)r=t;}return r;}
HatsuPointerKun
la source
Pouvez-vous retirer les accolades après la première boucle for?
Zacharý
Aussi, pourquoi avez-vous let de htoute façon?
Zacharý
@ Zacharý l et h était pour l'index de début et de fin du sous-tableau
HatsuPointerKun
3

R , 54 octets

a=b=0;for(x in scan()){a=max(x,a+x);b=max(a,b)};cat(b)

Essayez-le en ligne!

Algorithme tiré de: problème de sous-réseau maximum

R , 65 octets

y=seq(x<-scan());m=0;for(i in y)for(j in y)m=max(m,sum(x[i:j]));m

Essayez-le en ligne!

  • Lis x depuis stdin.
  • Définir ycomme index dex .
  • Itérer deux fois sur tous les sous-ensembles possibles non vides.
  • Comparer la somme d'un sous-ensemble avec m(initialement m=0).
  • Stockez la valeur maximale dans m.
  • Valeur d'impression de m.

R , 72 octets

n=length(x<-scan());m=0;for(i in 1:n)for(j in i:n)m=max(m,sum(x[i:j]));m

Essayez-le en ligne!

  • Lirex depuis stdin.
  • Effectuez une recherche complète sur tous les sous-ensembles possibles non vides.
  • Comparer la somme d'un sous-ensemble avec m(initialement m=0).
  • Stockez la valeur maximale dans m.
  • Valeur d'impression de m.

Autres idées infructueuses

58 octets

Reduce(max,lapply(lapply(seq(x<-scan()),tail,x=x),cumsum))

63 octets

Reduce(max,lapply(seq(x<-scan()),function(i)cumsum(tail(x,i))))

72 octets

m=matrix(x<-scan(),n<-length(x),n);max(apply(m*lower.tri(m,T),2,cumsum))
djhurio
la source
1
a=b=0fonctionne aussi. Vous devez également gérer l'impression de la sortie. Lorsqu'il est exécuté en tant que programme complet (via source), cela n'imprime rien.
JAD
@JarkoDubbeldam, j'ai ajouté cat(b), mais s'il provient de lui, echo=TRUEil suffit d'appeler bpour l'impression.
djhurio
Je suppose qu'il n'y a pas de définition claire sur la façon dont les programmes complets sont exécutés dans R. Il y a rscript en ligne de commande et la source dans R lui-même. Mais généralement, les indicateurs nécessaires à l'exécution d'un script sont inclus dans le bytecount. (Je n'ai pas personnellement réussi à faire fonctionner correctement script avec scan, mais c'est autre chose.
JAD
Vous pouvez utiliser T=Fau lieu de a=b=0pour enregistrer deux octets, car maxcontraindra bà numeric.
Giuseppe
3

Haskell , 28 octets

maximum.scanl((max<*>).(+))0

Essayez-le en ligne!

H.PWiz
la source
le maximum ne sera-t-il pas toujours le dernier élément du retour de scanl? alors foldl((max<*>).(+))0??
matthias
NVM je vois mon erreur!
matthias
@matthias Si vous voyez l'historique des modifications, vous verrez que j'ai fait l'erreur sma. :-)
H.PWiz
2

Mathematica, 24 octets

Max[Tr/@Subsequences@#]&
J42161217
la source
2

Haskell , 41 33 octets

import Data.List
g=maximum.concatMap(map sum.inits).tails
maximum.(scanl(+)0=<<).scanr(:)[]

Essayez-le en ligne! merci à Laikoni

michi7x7
la source
1
Les fonctions anonymes sont autorisées en tant que soumission, vous pouvez donc supprimer le g=. Au lieu de concatMapvous pouvez utiliser à =<<partir de la liste monade: Essayez-le en ligne! (33 octets).
Laikoni
1

Japt , 11 octets

£ãY mxÃc rw

Essayez-le en ligne!

Explication

£ãY mxÃc rw
m@ãY mx} c rw   // Ungolfed
m@     }        // Map the input array by the following function, with Y=index
  ãY            //   Get all subsections in input array length Y
     mx         //   Sum each subsection
         c rw   // Flatten and get max

Méthode alternative, 11 octets

De @ETHproductions; basé sur la réponse Husk de Brute Forces .

£sY å+Ãc rw

Obtient toutes les queues du tableau d'entrée et additionne chacune cumulativement. Aplatit ensuite le tableau et obtient le maximum.

Essayez-le en ligne!

Justin Mariner
la source
Nice, vraiment sympa. Je n'ai pas essayé d'implémenter ce défi quand je l'ai vu plus tôt, mais j'ai pensé à une technique différente et je m'attendais à ce qu'elle sorte environ 15 octets, donc c'est génial.
ETHproductions
En regardant la réponse Husk, il existe un autre moyen efficace: £sY å+Ãc rw(également 11 octets)
ETHproductions
@ETHproductions Plutôt sympa, j'ajouterai cela à cette réponse comme méthode alternative. Cela pourrait-il être amélioré avec une combinaison de réduction / concaturation, comme cette réponse Husk?
Justin Mariner
1

Rubis, 61 59 57 octets

Je viens de commencer à apprendre Ruby, c'est donc ce que j'ai trouvé.

s=0
p [gets.split.map{|i|s=[j=i.to_i,s+j].max}.max,0].max

J'ai vu cet algorithme pour la première fois dans la version finlandaise de ce livre inachevé . C'est très bien expliqué à la page 23.

Essayez-le en ligne!

Yytsi
la source
1

JavaScript, 58 octets

m=Math.max;x=y=>eval("a=b=0;for(k of y)b=m(a=m(a+k,k),b)")

Implémentation JS golfée de l'algorithme de Kadane. Fabriqué aussi court que possible. Ouvert aux suggestions constructives!

Ce que j'ai appris de ce post: la valeur de retour de eval- lorsque son dernier état est une forboucle - est fondamentalement la dernière valeur présente à l' intérieur de la boucle. Cool!

EDIT: économisé quatre octets grâce aux suggestions de Justin et Hermann.

Gaurang Tandon
la source
Vous pouvez éviter le returnen remplaçant {...;return b;}par eval("...;b")puisque eval renvoie la dernière instruction.
Justin Mariner
@JustinMariner merci! j'apprends toujours quelque chose de nouveau ici :)
Gaurang Tandon
Vous pouvez supprimer deux octets supplémentaires en supprimant ;b, car il est renvoyé de la boucle for
Herman L
@HermanLauenstein Oh, wow, thanks, that's useful!
Gaurang Tandon
0

Python 2, 52 51 bytes

f=lambda l:len(l)and max(sum(l),f(l[1:]),f(l[:-1]))

Try it online!

Sisyphus
la source
1
This seems to conflict (the otherwise unnecessary) requirement Don't read anything except stdin, and don't write to anywhere except stdout.
Mr. Xcoder
0

Common Lisp, 73 bytes

(lambda(a &aux(h 0)(s 0))(dolist(x a s)(setf h(max x(+ h x))s(max s h))))

Try it online!

Renzo
la source
0

k, 14 bytes

|/,/+\'(1_)\0,

Try it online!

            0, /prepend a zero (in case we're given all negatives)
       (1_)\   /repeatedly remove the first element, saving each result
    +\'        /cumulative sum over each result, saving each result
  ,/           /flatten (fold concat)
|/             /maximum (fold max)
zgrep
la source
0

APL, 31 29 27 bytes

⌈/∊∘.{+/W[X/⍨⍺≤X←⍳⍵]}⍨⍳⍴W←⎕

Try it online! (modified so it will run on TryAPL)

How?

  • ∊∘.{+/W[X/⍨⍺≤X←⍳⍵]}⍨⍳⍴W←⎕ Generate sums of subvectors
  • ⌈/ Maximum
Zacharý
la source
0

CJam, 24 bytes

q~:A,{)Aew{:+}%}%e_0+:e>

Function that takes array of numbers as input.

Try it Online

q~:A   e# Store array in 'A' variable
,{)Aew e# Get every possible sub-array of the array
{:+}%  e# Sum every sub array
}e_    e# flatten array of sums
0+     e# Add zero to the array
:e>    e# Return max value in array
geokavel
la source
0

MY, 11 bytes

⎕𝟚35ǵ'ƒ⇹(⍐↵

Try it online! MY is on TIO now! Woohoo!

How?

  • = evaluated input
  • 𝟚 = subvectors
  • 35ǵ' = chr(0x53) (Σ, sum)
  • ƒ = string as a MY function
  • = map
  • ( = apply
  • = maximum
  • = output with a newline.

Sum was fixed (0 on empty arrays) in order for this to work. Product was also fixed.

Zacharý
la source
0

J, 12 bytes

[:>./@,+/\\.

Similar to zgrep's K solution: the scan sum of all suffixes (produces a matrix), raze, take max

Try it online!

NOTE

for not too many more bytes, you can get an efficient solution (19 bytes golfed):

[: >./ [: ({: - <./)\ +/\
Jonah
la source
0

Axiom, 127 bytes

f(a:List INT):Complex INT==(n:=#a;n=0=>%i;r:=a.1;for i in 1..n repeat for j in i..n repeat(b:=reduce(+,a(i..j));b>r=>(r:=b));r)

This would be O(#a^3) Algo; I copy it from the C++ one... results

(3) -> f([1,2,3,-4,-5,6,7,-8,9,10,-11,-12,-13,14])
   (3)  24
                                                    Type: Complex Integer
(4) -> f([])
   (4)  %i
                                                    Type: Complex Integer
(5) -> f([-1,-2,3])
   (5)  3
                                                    Type: Complex Integer
RosLuP
la source
0

Scala, 105 bytes

val l=readLine.split(" ").map(_.toInt);print({for{b<-l.indices;a<-0 to b+2}yield l.slice(a,b+1).sum}.max)

I didn't find any better way to generate the sublists arrays.

6infinity8
la source
0

Java 8, 242 bytes

import java.util.*;v->{List a=new Stack();for(String x:new Scanner(System.in).nextLine().split(" "))a.add(new Long(x));int r=0,l=a.size(),i=l,j,k,s;for(;i-->0;)for(j=l;--j>1;r=s>r?s:r)for(s=0,k=i;k<j;)s+=(long)a.get(k++);System.out.print(r);}

Try it here.

106 bytes without using STDIN/STDOUT requirement.. >.>

a->{int r=0,l=a.length,i=l,j,k,s;for(;i-->0;)for(j=l;--j>1;r=s>r?s:r)for(s=0,k=i;k<j;s+=a[k++]);return r;}

Try it here.

Explanation:

import java.util.*;      // Required import for List, Stack and Scanner

v->{                     // Method with empty unused parameter and no return-type
  List a=new Stack();    //  Create a List
  for(String x:new Scanner(System.in).nextLine().split(" "))
                         //  Loop (1) over the STDIN split by spaces as Strings
    a.add(new Long(x));  //   Add the String converted to a number to the List
                         //  End of loop (1) (implicit / single-line body)
  int r=0,               //  Result-integer
      l=a.size(),        //  Size of the List
      i=l,j,k,           //  Index-integers
      s;                 //  Temp sum-integer
  for(;i-->0;)           //  Loop (2) from `l` down to 0 (inclusive)
    for(j=l;--j>1;       //   Inner loop (3) from `l-1` down to 1 (inclusive)
        r=               //     After every iteration: change `r` to:
          s>r?           //      If the temp-sum is larger than the current `r`:
           s             //       Set `r` to the temp-sum
          :              //      Else:
           r)            //       Leave `r` the same
      for(s=0,           //    Reset the temp-sum to 0
          k=i;k<j;)      //    Inner loop (4) from `i` to `j` (exclusive)
        s+=(long)a.get(k++);
                         //     Add the number at index `k` in the List to this temp-sum
                         //    End of inner loop (4) (implicit / single-line body)
                         //   End of inner loop (3) (implicit / single-line body)
                         //  End of loop (2) (implicit / single-line body)
  System.out.print(r);   //  Print the result to STDOUT
}                        // End of method
Kevin Cruijssen
la source