2020--07--17 单次买入卖出股票最大利润

题目描述
假设你有一个数组，其中第i个元素是某只股票在第i天的价格。
如果你最多只能完成一笔交易(即买一股和卖一股股票)，设计一个算法来求最大利润。

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 (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
示例1
输入
[1,4,2]
输出
3
这道题的思路是贪心算法
首先用一个greed方法，重新开一个数组来记录：当前第i天的最大利润，即第i天的值减去索引0到i-1的最小值
其次只需要返回新数组的最大值即可

代码实现：

//寻找数组0到index的最大值
    public int max(int[] A,int index){
        int max=A[0];
        for (int i = 1; i <= index; i++) {
            if (A[i]>max)max=A[i];
        }
        return max;
    }
//寻找数组0到index最小值
  public int min(int[] A,int index){
        int min=A[0];
        for (int i = 1; i <= index; i++) {
            if (A[i]<min)min=A[i];
        }
        return min;
    }
//贪心，用新数组profit记录当前最优
    public int greed(int[] A){
        int profit[] = new int[A.length];
        for (int i = 0; i < A.length; i++) {
            profit[i] = A[i]-min(A,i-1)>0? (A[i]-min(A,i-1)):0;
        }
        return max(profit,profit.length-1);//返回profit的最大值
    }
    public int maxProfit (int[] prices) {
        if (prices.length<=0)return 0;//空数组
        else
        return greed(prices);
    }