package y2019.Algorithm.array;

/**

 * @ProjectName: cutter-point

 * @Package: y2019.Algorithm.array

 * @ClassName: MaxProfit

 * @Author: xiaof

 * @Description:  121. Best Time to Buy and Sell Stock

 * Say you have an array for which the ith 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.

 *

 * Input: [7,1,5,3,6,4]

 * Output: 5

 * Explanation: 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.

 *

 * 说白了，这个题就是求最大差额，数组是每日的价格表，我们要选2天，买进和卖出，然后获取能获益的差额，而且卖只能在买进之后

 * @Date: 2019/7/2 9:42

 * @Version: 1.0

 */

public class MaxProfit {

    public int solution(int[] prices) {

        //这里有点想之前的dp一维数组的意思

        //我们只需要判断当前的数据和之前最小的那个数据的差值是否是更大

        int result = 0, small = 0;

        if(prices.length == 0)

            return 0;

        else {

            small = prices[0];

        }

        for(int i = 1; i < prices.length; ++i) {

            int temp = prices[i];

            //我们只需要判断当前的数据和之前最小的那个数据的差值是否是更大

            result = (temp - small) > result ? temp - small : result;

            if(temp < small) {

                small = temp;

            }

        }

        return result;

    }

    public static void main(String args[]) {

        int pres[] = {1,2};

        System.out.println(new MaxProfit().solution(pres));

    }

}