Easy puzzle, you have a list of values and are looking for the biggest loss possible, i.e the biggest difference between a high value, and a low value which follows it in the list. For this you just have to compute the difference between the current value and the maximum value read yet, and search for the biggest difference.
Difficulty: Medium · Skills: single pass, running maximum, greedy, array scan
Stock Exchange Losses is the inverted twin of the well known maximum profit interview problem. It checks whether you can find the biggest drop from an earlier peak to a later trough in one pass instead of comparing every pair.
One pass over n prices gives O(n) time and O(1) extra memory.
State the invariant out loud: best loss so far versus current price minus highest price seen so far. That single line is the whole solution and is easy to verify.
Note the usage of strtok and atoi to read all the integer values contained in a string.
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <limits.h>
int main(int argc, char **argv)
{
// number of stock values
int N;
scanf("%d\n", &N);
/* as each stock value is under 2^31 which is roughly 4*10^9,
15 chars per value is largely enough*/
char line[15*N];
fgets(line,15*N,stdin);
/* currentMax and currentMin will store the local minimum and maximum
stock values, maxLoss will store the maximum loss found yet */
int stockValue, maxLoss, currentMax, currentMin;
maxLoss = currentMax = 0;
currentMin = INT_MAX;
// Uses strtok to read all the stock values
char *tok;
tok = strtok(line," ");
for (int i = 0 ; i < N ; i++) {
stockValue = atoi(tok);
if (stockValue > currentMax) {
if (currentMax-currentMin > maxLoss)
maxLoss = currentMax-currentMin;
currentMax = currentMin = stockValue;
}
else if (stockValue < currentMin)
currentMin = stockValue;
tok = strtok(NULL," ");
}
if (currentMax-currentMin > maxLoss)
maxLoss = currentMax-currentMin;
printf("%d\n",-maxLoss);
return EXIT_SUCCESS;
}