## CodinGame - Solution in Javascript to Stock Exchange Losses Problem

This is a Javascript implementation for a solution to the CodinGame Stock Exchange Losses problem.

The post is the fourth in a series that I started with the goal of testing the feasibility of solving CodinGame challenges in Javascript. You can also check out the third and second solutions that I posted earlier.

```

var prices = [];                    // prices array will hold price values

// this is javascript
//   so we have to make sure the prices are interpreted as integers
for(var i = 0; i < prices.length; i++)
prices[i] = parseInt(prices[i]);

var localMinIdx = 0;
var localMaxIdx = 0;
var globalMinIdx = localMinIdx;
var globalMaxIdx = globalMinIdx;

// check all prices, looking for new local maximal difference
for (var i = 0; i < prices.length; i++)
{
// if a lower price is found than the global minimum so far
if(prices[i] < prices[globalMinIdx])
{
// update the global minimum
globalMinIdx = i;
}

// if the new price is larger than the current local maximum price
if(prices[i] > prices[localMaxIdx])
{
// start a new local min/max sequence
localMaxIdx = i;
localMinIdx = i;
}
// if the new price is lower than the current local minimum price
else if(prices[i] < prices[localMinIdx])
{
// update the local minimum price
localMinIdx = i;

// and compare the local difference to the global difference so far
var localDelta = prices[localMaxIdx] - prices[localMinIdx];
var globalDelta = prices[globalMaxIdx] - prices[globalMinIdx];

if(localDelta > globalDelta)
{
// the local difference is larger than the global difference
//  so make this the new global benchmark difference
globalMinIdx = localMinIdx;
globalMaxIdx = localMaxIdx;
}
}
}

// the maximum loss is the negative global delta
var maxLoss = prices[globalMinIdx] - prices[globalMaxIdx];

print(maxLoss);

```

There is a naive O(n^2) solution to this problem which compares each element to all subsequent elements keeping track of the global minimum (maximal difference) found. This is trivial to implement using two nested for loops

```
var maxLoss = 0;
for (var i = 0; i < prices.length; i++)
{
var min = prices[i];
for (var j = i + 1; j < prices.length; j++)
{
if(prices[j] < min)
{
min = prices[j];
}
}
if(maxLoss > (min - prices[i]))
{
maxLoss = (min - prices[i]);
}
}

// the desired result is the value of maxLoss
```

However, this algorithm is sub-optimal and it's quadratic performance characteristics start to take a toll on larger sequences.

In contrast with the trivial O(n^2) implementation, the algorithm I gave in the complete solution computes the result in linear time by keeping track of two differences: a local difference which is updated whenever a new larger price is detected, and a global difference which is the largest (maximal) difference for all prices so far

The original problem statement can be found on the CodinGame website.

is the founder of Donaq, a software development consulting company with a focus on mobility. You can find Mike on Google+ and on LinkedIn.