CareerCup

Let A be the input array.
Maintain another array AMin such that AMin[i] = min(A[i] ... A[n]), which can be done in linear time working backwards on A.

Now max(A[i] - AMin[i]) will be the maximum loss.

Ex:

A:     1 2 3 4 50 47 35 22 48 10 34 11
AMin:  1 2 3 4 10 10 10 10 10 10 11 11
Loss:  0 0 0 0 40 37 25 12 38 00 23 00

Linear solution in time

Go through the array in order, keeping track of the lowest stock price
and the best deal you've seen so far. Whenever the current stock price minus the
current lowest stock price is better than the current best deal, update the best deal
to this new value.

This is not my solution. A previous Question asked in Bloomberg section some what resembles the Question......
Maximum loss when we will buy at highest price and sell it at lowest price.
So Find decreasing intervals..If you couldn't find any such interval then maximum loss is zero....

int MAX_LOSS( int A[]){

int i=0;
int max_loss = 0;
for( i =0 to n){
int local_maxima = A[i];

while( A[i] > A[i+1]){
local_minima = A[i+1];
++i;
}

temp_max_loss = local_maxima - local_minima;

if(max_loss < temp_max_loss){
max_loss = temp_max_loss;
}

}
return max_loss;
}

Pretty simple....Imagine it to be a graph chart...Maintain a curr_max which stores the value of the spike above x-axis. A decreasing interval is present until a value higher than this occurs. FInd the min in that interval, the diff of which with curr_max will be our curr_max_loss. Do this for every decreasing interval updating curr_max_loss if necessary.

Did a similar problem with finding the HighestGainPossible.

static void FindHighestGain(int[] dailyStockValues)
        {
            int low, hi, possibleLow;
            low = hi = possibleLow = dailyStockValues[0];
            int lowIndex = 0, hiIndex = 0, possibleLowIndex = 0;

            Console.Write("Stock Values are: ");

            for (int i = 0; i < dailyStockValues.Length; i++)
            {
                Console.Write(dailyStockValues[i] + " ");

                // Update the hi value as we go forward.
                if (dailyStockValues[i] > hi)
                {
                    hi = dailyStockValues[i];
                    hiIndex = i;
                }

                // Track the possible low value.
                if (dailyStockValues[i] < possibleLow)
                {
                    possibleLow = dailyStockValues[i];
                    possibleLowIndex = i;
                }

                // Compare the possible max value with the current max.
                if ((dailyStockValues[i] - possibleLow) > (hi - low))
                {
                    // Set the new low
                    low = possibleLow;
                    lowIndex = possibleLowIndex;

                    // Set the new high
                    hi = dailyStockValues[i];
                    hiIndex = i;
                }
            }

            Console.WriteLine();
            Console.WriteLine("The maximum gain possible is: " + (hi - low));
            Console.WriteLine("LowIndex={0} HighIndex={1}", lowIndex, hiIndex);
        }

Finding maximum loss is doing the above going backwards in the array.

go through the list
for each value
if it is greater than current max, update current max,
if it is smaller than current max, find difference and update current max difference

int[] a = {1,2,3,4,5,6,7,7};
		int maxdiff=a[0]-a[1];
		int local_maximum= a[0];
		int diff =0;
		
		for(int i=0; i < a.length -1 ; i++){
			
			for(int j=a[i+1];j< a.length;j++){
				if(a[j]>local_maximum){
					local_maximum = a[j];
					i=j;
				}else{
					diff = a[i] - a[j];
					if(diff > maxdiff){
					
						maxdiff = diff;
					}						
				}
			}
		}
		
	 return maxdiff;
	}