## The challenge

Say you have an array for which the *i*^{th} element is the price of a given stock on day *i*.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

**Example 1:**

Input:[7,1,5,3,6,4]Output:5Explanation:Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Not 7-1 = 6, as selling price needs to be larger than buying price.

**Example 2:**

Input:[7,6,4,3,1]Output:0Explanation:In this case, no transaction is done, i.e. max profit = 0.

## The solution in Java

```
class Solution {
public int maxProfit(int[] prices) {
// create a profit variable to return
int maxprofit = 0;
// loop through the original array
for (int i=0; i<prices.length-1; i++) {
// loop through the array from the next item on
for (int j=i+1; j<prices.length; j++) {
// if in bounds and next is greater than current
if (j<prices.length && prices[j]>prices[i]) {
// work out profit
int tmp = prices[j]-prices[i];
// report the profit
if (tmp>maxprofit) maxprofit = tmp;
}
}
}
// return out profit
return maxprofit;
}
}
```