Codingame Solution: Stock Exchange Losses

18 Dec 2022 Robert Eisele

The Goal

A finance company is carrying out a study on the worst stock investments and would like to acquire a program to do so. The program must be able to analyze a chronological series of stock values in order to show the largest loss that it is possible to make by buying a share at a given time t0 and by selling it at a later date t1. The loss will be expressed as the difference in value between t0 and t1. If there is no loss, the loss will be worth 0.

Game Input

Input

Line 1: the number n of stock values available.

Line 2: the stock values arranged in order, from the date of their introduction on the stock market v₁ until the last known value v_n. The values are integers.

Output

The maximal loss p, expressed negatively if there is a loss, otherwise 0.

Constraints

0 < n < 100000
0 < v < 2³¹

VB.net Solution

Based on the first point p we got, we subtract the second point q. If q is smaller than p, we have a loss. What we now must do is maximizing the loss, so we'll go from point to point and compare the currently highest point p with every new point q. Since we can find a new high with every new point we get, we also have to maximize p. I thought visually about this problem. Look at this graph:

Imagine, you put a straight line between the first and the second point. Now you keep the first point fixed as an anker and rotate the line to the third point. That one is higher than the second, and as such the loss is less than the already known. Now we have a new high and let the third point be the anker and go down to the fourth and fifth. We now found a new maximum loss. With the next point we have to move the anker point again and the game goes on. When implemented, it's as simple as the following VB.net snippet:

Module Solution

    Sub Main ()

        Dim n as Integer
        n = Console.ReadLine()

        Dim vs(n) as String
        vs = Console.ReadLine().split(" ")

        Dim p as Integer
        Dim d as Integer

        p = Convert.toInt32(vs(0))
        d = 0

        For Each v As String In vs
            Dim t as Integer

            t = Convert.toInt32(v)
            d = Math.max(d, p - t) ' max loss
            p = Math.max(p, t) ' max seen value
        Next

        Console.WriteLine(- d)

    End Sub
End Module

It's also possible to reverse the idea so that the negation at the end isn't necessary:

Module Solution

Sub Main ()

    Dim n as Integer
    n = Console.ReadLine()

    Dim vs(n) as String
    vs = Console.ReadLine().split(" ")

    Dim p as Integer
    Dim d as Integer

    p = Convert.toInt32(vs(0))
    d = 0

    For Each v As String In vs
        Dim t as Integer

        t = Convert.toInt32(v)
        d = Math.min(d, t - p) ' max loss
        p = Math.max(p, t) ' max seen value
    Next

    Console.WriteLine(d)

End Sub
End Module

Alternatively, a two-pass solution is possible by finding the index of the minimum element first and then find the maximum up to the index of the minimum element. The maximum loss would be the difference between this minimum and maximum. However, the one-pass solution described above is much more efficient.

Codingame Solution: Stock Exchange Losses

The Goal

Game Input

VB.net Solution

Related Stuff

Codingame Solution: Factorial vs Exponential

Codesignal Solution: Minimum Jump To Reach End

Hackerrank Solution: Maximizing XOR