Stock Zeitmaschine

Sie haben Zugriff auf einen Datensatz, tomorrowStocksder die Aktienkurse Ihres Lieblingsgeschäfts an der NASDAQ enthält. Dieser Datensatz ist ein Container, der nach Minuten nach dem Öffnen indiziert wird. Jeder Index enthält den Preis der Aktie zu diesem Zeitpunkt.

// Assume the stock market opens at 9:30AM EDT
// tomorrowStocks[] contains the prices of your target stock.
// If the stock is $22 @ 10:30AM EDT
tomorrowStocks[60] == 22

Ausgabe

Ihre Aufgabe ist es, das bestmögliche Ergebnis zu bestimmen , 1 purchaseund 1 saleder 1 stockaus dem gegebenen Datensatz.

Fallstricke

• Sie müssen genau 1 Aktie kaufen und verkaufen.
• Sie können möglicherweise nicht im selben Zeitfenster kaufen und verkaufen.
• Sie müssen kaufen, bevor Sie verkaufen.

Testdaten

[1,2,3,4,5]    # 4
[1,99,2,105]   # 104
[99,1,99,100]  # 99
[99,1,1,2,1,3] # 2
[5,4,3,3,1]    # 0
[5,4,3,1]      # -1
[5,2,1]        # -1
[5,4,1]        # -1
[55,45,20,1]   # -10
[5,1]          # -4
[10,7,5,1]     # -2
[7]            # Invalid input -- assume size >= 2

Dies ist ein Code-Golf ; Senden Sie die kürzeste Antwort in Ihrer Lieblingssprache!

05AB1E , 4 Bytes

Verwendung des FryAmTheEggman-Ansatzes . Code:

¥ŒOà

Erläuterung:

¥     # Calculate the increments of the array.
 Π   # Get all substring of the array.
  O   # Sum the arrays in the array.
   à  # Get the largest sum and implicitly print that.

Verwendet die CP-1252- Codierung. Probieren Sie es online! .

Python 2, 46 Bytes

f=lambda x:-min(x.pop(0)-max(x),x[1:]and-f(x))

Teste es auf Ideone .

Wie es funktioniert

Hierbei handelt es sich um einen rekursiven Ansatz, bei dem die wunderbar perversen gemischten Vergleiche von Python 2 ausgenutzt werden.

Das bestmögliche Ergebnis ist entweder die Differenz des Maximums der Liste, bei der das erste Element entfernt wurde, und des ersten Elements, oder eine andere Differenz, bei der das erste Element nicht betroffen ist.

Nach dem Extrahieren des ersten Elements mit x.pop(0)(das es endgültig aus x entfernt ) berechnen wir x.pop(0)-max(x). Beachten Sie, dass dieser Unterschied das "falsche" Vorzeichen hat.

Wenn die aktualisierte Liste x noch mindestens zwei Elemente enthält, wird x[1:]eine nicht leere Liste erstellt und anddurch das Negativ eines rekursiven Aufrufs ersetzt, der wie folgt berechnet wird -f(x). Wenn zu wenige Elemente vorhanden sind, um fortzufahren, wird x[1:]and-f(x)eine leere Liste ausgewertet.

Um das maximale Ergebnis auszuwählen, nehmen wir das Minimum der Differenz und das Negativ des rekursiven Aufrufs (oder []). Da alle ganzen Zahlen streng kleiner als sind [], minwird einfach das linke Argument zurückgegeben, wenn das rechte ist [].

Schließlich -korrigiert das unäre Minus das Vorzeichen des berechneten Ergebnisses.

MATL , 7 Bytes

2XN!dX>

Probieren Sie es online! Oder überprüfen Sie alle Testfälle .

2XN  % Take input implicitly. Two-column 2D array with all combinations of 2 elements.
     % Each combination is a row. Elements in each row are in increasing order
!    % Transpose
d    % Difference of the two numbers in each column
X>   % Maximum value. Display implicitly

Gelee , 5 Bytes

Œcḅ-Ṁ

Probieren Sie es online! oder überprüfen Sie alle Testfälle .

Wie es funktioniert

Œcḅ-Ṁ  Main link. Argument: A (integer array)

Œc     Generate all combinations of two elements of A, in order.
  ḅ-   Convert each pair from base -1 to integer.
       This maps [a, b] to b - a.
    Ṁ  Take the maximum of all computed differences.

Pyth, 9

eSsM.:-Vt

Probieren Sie es hier aus oder führen Sie eine Test Suite aus .

Findet die aufeinanderfolgenden Unterschiede zwischen den einzelnen Elementen und findet dann jede Teilzeichenfolge dieses Arrays. Zum Schluss summieren Sie die Elemente und geben das Maximum zurück.

Erläuterung:

eSsM.:-Vt
eSsM.:-VtQQ   ## Auto-fill variables
      -VtQQ   ## Splat subtraction on each element of zip(Q[1:], Q)
    .:        ## Get all substrings
  sM          ## Sum each list
eS            ## Take the largest number

Mir wurde gesagt, dass dieser Algorithmus nicht ganz intuitiv funktioniert. Hoffentlich zeigt dieses Beispiel, warum dieser Algorithmus funktioniert:

[a, b, c, d]
difference between each element (reversed because of how Pyth does this)
[b-a, c-b, d-c]
"substrings" or each continuous slice
[b-a], [c-b], [d-c], [b-a, c-b], [c-b, d-c], [b-a, c-b, d-c]
sum each
[b-a], [c-b], [d-c], [b-a+c-b], [c-b+d-c], [b-a+c-b+d-c]
simplify
[b-a], [c-b], [d-c], [c-a], [d-b], [d-a]

Pyth, 9

_hS-M.cQ2

Yay pfns!

_hS-M.cQ2

     .cQ2 # generate all 2-elements combinations of Q (argument)
   -M     # map-splat with -: for each combination, substract the elements together
  S       # tort
 h        # take the first
_         # absolute value

PowerShell v2 +, 58 Byte

param($n)($n|%{($n[++$i..$n.count]|sort)[-1]-$_}|sort)[-1]

Übernimmt die Eingabe $nund leitet jedes Element in eine Schleife |%{...}. Bei jeder Iteration schneiden wir $nbasierend auf dem ++$ibis zum Ende des Eingabearrays vorinkrementierten Wert, |sortnehmen das Maximum [-1]und subtrahieren dann das aktuelle Element $_. Wir nehmen dann |sortalle diese Unterschiede und wieder das Maximum [-1].

Wirft einen ausführlichen Array-Index-Fehler aus, da versucht wird, das Ende des Arrays zu überschreiten. Da STDERR jedoch standardmäßig ignoriert wird , ist es uns egal.

JavaScript (ES6), 57 54 Bytes

a=>(m=Math.max)(...a.map((x,i)=>m(...a.slice(i+1))-x))

In JavaScript ist es einfacher, das Maximum des restlichen Arrays zu nehmen und das aktuelle Element zu subtrahieren. (Beim letzten Element ist das Ergebnis weiterhin -Infinity.) Bearbeiten: 3 Byte dank @CharlieWynn gespeichert.

J, 21 Bytes

[:>./@;i.@#<@{."_1-/~

Nimmt ein Array von Werten als Argument und gibt das Ergebnis zurück.

Erläuterung

[:>./@;i.@#<@{."_1-/~  Input: p
                  -/~  Make a table of all differences between every pair
          #            Get the count of values in p
       i.@             Create a range [0, 1, ..., len(p)-1]
             {."_1     Take that many values from each row of the table
           <@          Box each row of selected values
[:    ;                Unbox and concatenate them
  >./@                 Reduce it by the max and return

Java, 141 Bytes

a->java.util.stream.IntStream.range(0,a.size()-1).map(i->a.subList(i+1,a.size()).stream().reduce(Math::max).get()-a.get(i)).max().getAsInt();

Das Lambda akzeptiert eine ArrayList und gibt eine Ganzzahl zurück.

Ungolfed Code mit Testfällen:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.function.Function;
import java.util.stream.IntStream;

class Test {

    public static void main(String[] args) {
        Function<ArrayList<Integer>, Integer> f = a -> IntStream
            .range(0, a.size()-1)
            .map(i -> a.subList(i+1, a.size()).stream().reduce(Math::max).get() - a.get(i))
            .max()
            .getAsInt();

        System.out.println(f.apply(new ArrayList<>(Arrays.asList(1,2,3,4,5))));
        System.out.println(f.apply(new ArrayList<>(Arrays.asList(1,99,2,105))));
        System.out.println(f.apply(new ArrayList<>(Arrays.asList(99,1,99,100))));
        System.out.println(f.apply(new ArrayList<>(Arrays.asList(99,1,1,2,1,3))));
        System.out.println(f.apply(new ArrayList<>(Arrays.asList(5,4,3,3,1))));
        System.out.println(f.apply(new ArrayList<>(Arrays.asList(5,4,3,1))));
        System.out.println(f.apply(new ArrayList<>(Arrays.asList(5,2,1))));
        System.out.println(f.apply(new ArrayList<>(Arrays.asList(5,4,1))));
        System.out.println(f.apply(new ArrayList<>(Arrays.asList(55,45,20,1))));
        System.out.println(f.apply(new ArrayList<>(Arrays.asList(5,1))));
        System.out.println(f.apply(new ArrayList<>(Arrays.asList(10,7,5,1))));
    }
}

Soweit ich weiß, hat Java keine Möglichkeit, in einem Stream nach vorne zu schauen, und die Methode, mit der der Stream generiert wird, zu manipulieren, führt zu merkwürdigen Ergebnissen. Wenn Sie also a.remove(0)in einer Karte arbeiten, wird der Stream fürchterlich unterbrochen.

VBA, 154

Übernimmt die Eingabe in Spalte A ab A1, gibt in C1 aus. Muss mit der zuletzt ausgewählten Zelle in A ausgeführt werden. Beachten Sie, dass Excel die Leerzeichen zwischen den Begriffen in VBA automatisch hinzufügt, andernfalls könnte dies weiter verbessert werden.

Sub s
i = Selection.Row
r = "B1:B" + i-1
Range(r).FormulaArray = "MAX(A2:A$" + i + "-A1)"
Range(r).FillDown
Range("C1").Formula = "MAX(" + r + ")"
End Sub

Java, 116

Eine andere Java-Lösung, ich habe diese verwendet, um zu beweisen, dass Streams zwar gut aussehen, aber nicht immer zum Golfen nützlich sind.

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

Diese Lösung bietet viel Raum für Verbesserungen

Clojure, 99 Bytes

(fn[x](apply max(map #(-(apply max(% 1))(apply min(% 0)))(map #(split-at % x)(range 1(count x))))))

Teilt die Eingabeliste an erster Stelle, dann an zweiter Stelle und so weiter, sodass wir eine Liste erhalten, die so aussieht:

[[[n1][n2 ... nk]][[n1 n2][n3 ... nk]]...[[n1...n(k-1)][nk]]]dann subtrahiert man für jedes Paar das Minimum der ersten Elemente von dem Maximum des zweiten Elements und findet dann das Maximum von ihnen. Wäre kürzer, wenn Clojures min maxSequenzen anstelle einer beliebigen Anzahl von Argumenten verwenden würden.

Sehen Sie es online: https://ideone.com/b2nllT

Rubin, 52 Bytes

->a{b=[];(x=a.pop;b+=a.map{|v|x-v})while a[0];b.max}

Knallt mögliche Verkaufspreise und schaut euch alle vorherigen an, um Gewinn zu erzielen. Dann bekommt man maximalen Gewinn.

C 101 99 Bytes

int i,j,m,h;int f(int*a){m=1<<31;for(;a[i];i++){for(j=i+1;a[j];h=a[j++]-a[i],m=h<m?m:h);}return m;}

Eingabe: nullterminiertes Array. ZB {1,2,3,4,5,0}
Ausgabe: Gibt das beste Ergebnis zurück

Sie können 8 Bytes einsparen ( 93 91 insgesamt), wenn Sie niemals Geld verlieren möchten:

int i,j,m,h;int f(int*a){for(;a[i];i++){for(j=i+1;a[j];h=a[j++]-a[i],m=h<m?m:h);}return m;}

R, 58 44 Bytes

max(unlist(sapply(seq(y<-scan()),diff,x=y)))

ungolfed

y=scan()                #input
s=1:length(y)           #sequence of same length from 1
l = sapply(s,diff,x=y)  #applies the function diff to each 'lag' in sequence s
                        #and differencing on y
max(unlist(l))          #reforms as vector and finds maximum

EDIT: Funktion geändert. Original unten.

f=function(x)max(max(x[-1]-x[1]),if(length(x)-2)f(x[-1]))

oder, wenn Sie bereit sind, eine Reihe von Warnmeldungen zu ertragen, entfernen Sie die Angabe -2 after length für 56 Byte.

f=function(x)max(max(x[-1]-x[1]),if(length(x))f(x[-1]))

Und wenn Sie das Gefühl haben, nicht zu handeln und Geld zu verlieren, wenn dies die einzige Möglichkeit ist, können Sie bis zu 52 Punkte erreichen

f=function(x)max(max(x-x[1]),if(length(x))f(x[-1]))