Maximum Single Transaction Profit

Given an integer array representing stock prices over consecutive days, your task is to compute the maximum profit from a single buy-and-sell transaction. You must buy before you sell. If no profit can be made, the result should be 0.

The problem can be solved in \(O(n)\) time by iterating through the prices, keeping track of the minimum price seen so far and calculating the profit if selling on the current day.

inputFormat

The first line contains a single integer (n) (the number of days). The second line contains (n) space-separated integers, where each integer represents the stock price on that day.

outputFormat

Output a single integer representing the maximum profit that can be achieved with one transaction. If no profit is possible, output 0.## sample

6
7 1 5 3 6 4

5