Stock Time Machine

Question

Stock Time Machine

You've gained access to a dataset, tomorrowStocks, which contains the stock prices from your favorite business on the NASDAQ. This dataset is a container indexed by minutes past opening. Each index contains the price of the stock at that time.

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

Output

Your task is to determine the best possible outcome of 1 purchase and 1 sale of 1 stock from the given dataset.

Gotchas

• You must buy and sell exactly 1 stock.
• You may not buy and sell in the same time slot.
• You must buy before you sell.

Test Data

[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

This is a code-golf; submit the shortest answer in your favorite language!

Answer 1

Python 2, 46 bytes

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

Test it on Ideone.

How it works

This is a recursive approach that takes advantage of Python 2's beautifully perverse mixed-type comparisons.

The best possible outcome is either the difference of the maximum of the list with its first element removed and that first element, or another difference that does not involve the first element.

After extracting the first element with x.pop(0) (which permanently removes it from x), we compute x.pop(0)-max(x). Note that this difference has the "wrong" sign.

If the updated list x still contains at least two elements, x[1:] yields a non-empty list, and and replaces it with the negative of a recursive call, computed as -f(x). Once there are too few elements to continue, x[1:]and-f(x) evaluates to an empty list.

To select the maximal outcome, we take the minimum of the difference and the negative of the recursive call (or []). Since all integers are strictly less than [], min will simply return its left argument if the right one is [].

Finally, the unary minus - corrects the sign of the computed outcome.

Answer 2

05AB1E, 4 bytes

Using FryAmTheEggman's approach. Code:

¥ŒOà

Explanation:

¥     # 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.

Uses the CP-1252 encoding. Try it online!.

Answer 3

MATL, 7 bytes

2XN!dX>

Try it online! Or verify all test cases.

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

Answer 4

Jelly, 5 bytes

Œcḅ-Ṁ

Try it online! or verify all test cases.

How it works

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

Answer 5

Pyth, 9

eSsM.:-Vt

Try it here or run a Test Suite.

Finds the consecutive differences between each element, then finds each substring of that array. Finally, sum the elements and return the maximal one.

Explanation:

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

It was mentioned to me that that this algorithm works isn't entirely intuitive. Hopefully this example will illustrate why this algorithm works:

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

Answer 6

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

Answer 7

PowerShell v2+, 58 bytes

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

Takes input $n, pipes each element into a loop |%{...}. Each iteration, we slice $n based on pre-incremented ++$i to the end of the input array, |sort that, and take the maximal [-1], then subtract the current element $_. We then |sort all of those differences, and again take the maximal [-1].

Tosses out a verbose array-index error, because we try to slice past the end of the array. But, since STDERR is ignored by default, we don't care.

Answer 8

JavaScript (ES6), 57 54 bytes

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

In JavaScript it's easier to take the max of the remainder of the array and subtract the current element. (In the case of the last element the result will still be -Infinity.) Edit: Saved 3 bytes thanks to @CharlieWynn.

Answer 9

J, 21 bytes

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

Takes an array of values as an argument and returns the result.

Explanation

[:>./@;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

Answer 10

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

The lambda accepts an ArrayList and returns an Integer.

Ungolfed code with test cases:

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

As far as I know, Java doesn't have a way to look forward in a stream, and manipulating the method from which the stream is generated produces strange results. So doing a.remove(0) inside a map horribly breaks the stream.

Answer 11

VBA, 154

Takes in the input in column A starting in A1, outputs in C1. Must be run with the last cell in A selected. Note that Excel auto-adds the spaces between terms in VBA, otherwise this could be golfed further.

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

Answer 12

Java, 116

Another java solution, i used this one to prove that, streams might looks nice, but not always useful for golfing.

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

there is lot of space for improvements in this solution

Answer 13

Clojure, 99 bytes

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

Splits input list at first position then second and so on, so we get a list which looks like this:

[[[n1][n2 ... nk]][[n1 n2][n3 ... nk]]...[[n1...n(k-1)][nk]]] then for each pair subtracts minimum of the first elements from max of the second element and then find max from them. Would be shorter if Clojure's min max were taking sequences rather than any number of arguments.

See it online: https://ideone.com/b2nllT

Answer 14

ruby, 52 bytes

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

pops possible sell prices and look at all of the previous to find profit. Then gets max profit.

Answer 15

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

Input: null terminated array. E.g. {1,2,3,4,5,0}
Output: returns the best outcome

You can save 8 bytes (93 91 total) if you never want to lose money:

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

Answer 16

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: changed function. original below.

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

or, if you're willing to put up with a bunch of warning messages, get rid of the -2 after length, for 56 bytes.

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

And if you feel like not trading and losing money when that's the only possibility, you can get down to 52

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