Definieren Sie das "maximale Unterarray" eines bestimmten Arrays als "ein (aufeinanderfolgendes) Unterarray mit der größten Summe". Beachten Sie, dass es keine "Nicht-Null" -Anforderung gibt. Gib diese Summe aus.

Geben Sie nach Möglichkeit eine Beschreibung Ihres Codes an.

Beispieleingang 1:

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

Beispielausgabe 1: 24

Beschreibung 1:
Die größte Summe ergibt sich durch Ausschneiden 6 7 -8 9 10und Aufsummieren.

Beispiel Eingabe 2: -1 -2 -3
Beispiel Ausgabe 2: 0
Beschreibung 2: Es ist einfach :) Ein leeres Subarray ist das "größte".

Anforderung:

• Lies nichts außer stdin und die Ausgabe sollte auf stdout gehen.
• Standard Lücken Einschränkungen gelten.

Ranking: Das kürzeste Programm gewinnt diesen Code-Golf .

Schale , 6 4 Bytes

▲ṁ∫ṫ

Probieren Sie es online!

      -- 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

Python 3 , 61 Bytes

a=b=0
for x in eval(input()):a=max(x,a+x);b=max(a,b)
print(b)

Probieren Sie es online!

Algorithmus aus Wikipedia gestohlen .

Pyth , 8 Bytes

eS+0sM.:

Probieren Sie es online!

Wie?

eS + 0sM .: Q - Q ist implizit, dh Eingabe. Nehmen wir an, es ist [-1, -2, -3].

      .: - Alle zusammenhängenden nicht leeren Unterlisten. Wir haben [[-1], [-2], [-3], [-1, -2], [-2, -3], [-1, -2, -3]].
    sM - Ermittelt die Summe jeder Unterliste. [-1, -2, -3, -3, -5, -6]
  +0 - Hängt eine 0 an die Summenliste an. [0, -1, -2, -3, -3, -5, -6]
eS - Maximales Element. S gibt uns [-6, -5, -3, -3, -2, -1, 0], während e 0, das letzte Element, zurückgibt.

05AB1E , 4 Bytes

Ό0M

Probieren Sie es online!

-1 danke an Adnan .

Gelee , 6 Bytes

ẆS€;0Ṁ

Probieren Sie es online!

C ++, 197 195 187 Bytes

-10 Bytes dank 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;}

R , 54 Bytes

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

Probieren Sie es online!

Algorithmus entnommen aus: Maximales Subarray-Problem

R , 65 Bytes

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

Probieren Sie es online!

• Lesen Sie xvon stdin.
• Stellen Sie yals Index x.
• Iterieren Sie zweimal über alle möglichen nicht leeren Teilmengen.
• Vergleichen Sie die Summe einer Teilmenge mit m(anfangs m=0).
• Speichern Sie den Maximalwert in m.
• Druckwert von m.

R , 72 Bytes

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

Probieren Sie es online!

• Lesen Sie xvon stdin.
• Führen Sie eine vollständige Suche über alle möglichen nicht leeren Teilmengen durch.
• Vergleichen Sie die Summe einer Teilmenge mit m(anfangs m=0).
• Speichern Sie den Maximalwert in m.
• Druckwert von m.

Andere erfolglose Ideen

58 Bytes

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

63 Bytes

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

72 Bytes

m=matrix(x<-scan(),n<-length(x),n);max(apply(m*lower.tri(m,T),2,cumsum))

Haskell , 28 Bytes

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

Probieren Sie es online!

05AB1E , 4 Bytes

-2 Bytes dank Adnan

ÎŒOM

Probieren Sie es online!

Mathematica, 24 Bytes

Max[Tr/@Subsequences@#]&

Haskell , 41 33 Bytes

import Data.List
g=maximum.concatMap(map sum.inits).tails

maximum.(scanl(+)0=<<).scanr(:)[]

Probieren Sie es online! danke an laikoni

Japt , 11 Bytes

£ãY mxÃc rw

Probieren Sie es online!

Erläuterung

£ã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

Alternative Methode, 11 Bytes

Aus @ETHproductions; basierend auf der Antwort von Brute Forces 'Husk .

£sY å+Ãc rw

Ruft alle Endpunkte des Eingabearrays ab und summiert sie kumulativ. Dann wird das Array abgeflacht und die max.

Probieren Sie es online!

Ruby, 61 59 57 Bytes

Ich habe gerade angefangen, Ruby zu lernen, also habe ich mir das ausgedacht.

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

Ich habe diesen Algorithmus zum ersten Mal in der finnischen Version dieses unvollendeten Buches gesehen . Dies wird auf Seite 23 sehr gut erklärt.

Probieren Sie es online!

JavaScript, 58 Byte

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

Golfed JS-Implementierung von Kadanes Algorithmus. So kurz wie möglich gemacht. Offen für konstruktive Vorschläge!

Was ich aus diesem Beitrag gelernt habe: Rückgabewert von eval- wenn seine letzte Anweisung eine forSchleife ist - ist im Grunde der letzte Wert, der in der Schleife vorhanden ist. Cool!

BEARBEITEN: Vier Bytes gespart dank Justins und Hermanns Vorschlägen.

Gaia , 6 Bytes

0+ḋΣ¦⌉

Probieren Sie es online!

Python 2 , 52 51 Bytes

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

Probieren Sie es online!

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))))

Probieren Sie es online!

k , 14 Bytes

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

Probieren Sie es 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)

APL, 31 29 27 Bytes

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

Probieren Sie es online! (geändert, damit es auf TryAPL läuft)

Wie?

• ∊∘.{+/W[X/⍨⍺≤X←⍳⍵]}⍨⍳⍴W←⎕ Generieren Sie Summen von Subvektoren
• ⌈/ Maximal

CJam, 24 Bytes

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

Funktion, die ein Array von Zahlen als Eingabe verwendet.

Probieren Sie es 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

MEIN , 11 Bytes

⎕𝟚35ǵ'ƒ⇹(⍐↵

Probieren Sie es online! MY ist jetzt bei TIO! Woohoo!

Wie?

• ⎕ = ausgewerteter Eingang
• 𝟚 = Subvektoren
• 35ǵ'= chr(0x53)(Σ, Summe)
• ƒ = string als MY-Funktion
• ⇹ = Karte
• ( = bewerben
• ⍐ = maximal
• ↵ = Ausgabe mit einem Zeilenumbruch.

Die Summe wurde ( 0bei leeren Arrays) korrigiert, damit dies funktioniert. Produkt wurde auch behoben.

J, 12 Bytes

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

Ähnlich wie bei der K-Lösung von zgrep: Die Scan-Summe aller Suffixe (ergibt eine Matrix), raze, take max

Probieren Sie es online!

HINWEIS

Für nicht zu viele Bytes erhalten Sie eine effiziente Lösung (19 Bytes Golf):

[: >./ [: ({: - <./)\ +/\

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)

Dies wäre O (# a ^ 3) Algo; Ich kopiere es aus dem C ++ ein ... Ergebnisse

(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

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)

Ich fand keinen besseren Weg , um die Unter erzeugen Listen Arrays.

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);}

Probieren Sie es hier aus.

106 Bytes ohne Verwendung der STDIN / STDOUT-Anforderung ..>.>

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;}

Probieren Sie es hier aus.

Erläuterung:

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