Given an array, its ith element is the price of a given stock on the ith day.

If you only allow one trade (buy and sell one stock), design an algorithm to calculate the maximum profit you can make.

Note that you can’t sell a stock before you buy it.

Example 1:

Input: [7,1,5,3,6,4] output: 5 explanation: buy on day 2 (stock price = 1) and sell on day 5 (stock price = 6), maximum profit = 6-1 = 5. Note that the profit cannot be 7-1 = 6, because the selling price needs to be greater than the buying price.Copy the code

Example 2:

Input: [7,6,4,3,1] output: 0 explanation: in this case, no transaction is completed, so the maximum profit is 0.Copy the code
class Solution {
    public int maxProfit(int[] prices) {
       if( prices.length == 0 ) return 0;
       int max = 0;
       int cur = prices[ 0 ]; 
       for( int price : prices ){
           if( price <= cur ){
               cur = price;
               continue;
           }
           max = Math.max( max ,  price - cur);
       } 
       returnmax; }}Copy the code

The cur variable is used to record the minimum value of the traversal. If the current value is greater than cur, the maximum value is updated. If it is greater than cur, the cur value is updated.