题解 | #买卖股票的最好时机(一)#

1. 假设每天都会卖出股票，使用dp[ ]来记录每天的最大利润；则dp[i] = prices[i]-买入价格
2. 那什么时候买入(才能让利润最大化)呢？ 使用一个min来记录买入股票价格 (默认初始化min=prices[0])

• 若当天的股票价格<min， 则min=prices[i] 即：当天买入,当天卖出--->dp[i] = 0
• 若当天的股票价格>=min，则使用之前买入的价格,当天卖出-->dp[i] = prices[i]-min

3. 返回dp[i]中的最大的那个就行了。

    买卖股票的最好时机
    我们需要选择一天买入，选择一天卖出。最后使我们的收益最大化
 XX 1.遍历每一天的最大利益情况
     O(n^2),遍历每一个位置,并遍历前面的所有位置,求出最大差值
             得到每个位置的最大利润
             
    2.假设每一天都尝试卖出,返回利润最大的那一天
        用一个dp数组记录每一天的最大利润, 用一个min记录(从第一天到当天)的最小股票价格
        第一天利润 为0 （min初始化为第一天的股票价格, price[0]-min=0）
        第二天利润 若股票价格<min,则维护min，且利润为0(买入min,又卖出price[1])
                  若股票价格>min,说明之前有更低的股票价格, 利润=price[1]-min
        每一天都先 维护min, 然后记录利润
    */
    public int maxProfit (int[] prices) {
        int min = prices[0]; //记录一个最小股票价格
        int[] dp = new int[prices.length]; //dp记录每一天的最大利润
        int max=0;
        for(int i=0;i<prices.length;i++){
            if(prices[i]<min){
                min = prices[i]; //维护最小股票价格
            }
            dp[i] = prices[i]-min; //记录当天的最大利润
            max = Math.max(max,dp[i]);
        }
        return max;
    }