121.买卖股票的最佳时机

原题地址：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/

题解

思路源自官方题解

开一个selled数组，selled[n]表示第n天卖出时的最高成交价

用一个min记录下遍历至n天时的历史最低价

自然地，当我们遍历到第n天时，selled[n]=prices[n]-min

再用一个max记录下最大的selled[n]即可

时间复杂度：O(n)

空间复杂度：O(n)

class Solution {
    public int maxProfit(int[] prices) {
        int min=99999;
        int max=0;
        int[] selled=new int[prices.length];
        for(int i=0;i< prices.length;i++){
            if(min>prices[i]){
                min=prices[i];
            }
            selled[i]=prices[i]-min;
            if(max<selled[i]){
                max=selled[i];
            }
        }
        return max;
    }
}