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

动态规划
什么时候能够得到最大利润？最低价格买入，最高价格卖出，且买入时间早于卖出时间。
i从0开始计数，dp[i]代表在第i天卖出时，能够获取的最大利润。同时需要一个变量mi，作为前面i-1天内，最低价格，这个可以放在循环内更新。
所以，dp[0]=0， 因为第0天只能当天买入，当天卖出。
dp[i]就有以下两种情况：
如果第i天的价格比mi还低，那么第i天卖出一定是亏的，dp[i]是个负数，由于题目要求最大值，我们可以将亏损的钱不计算，直接赋值为0.
如果第i天的价格比mi高，那么第i天卖出，最大利润一定是（第i天的价格-mi）
注意，在循环时候需要设置一个ans，每次算出dp[i]时， ans = Math.max(ans,dp[i])，这样ans就是返回值。

public int maxProfit (int[] prices) {
    // write code here
    if(prices.length<=1){
        return 0;
    }
    int mi = prices[0];
    int [] dp = new int[prices.length];
    dp[0] = 0;
    int ans =0 ;
    // dp[i]表示第i天卖出最大利润
    for(int i=1; i < prices.length ; i++){
        if(prices[i]<mi){
            dp[i]=0;
            mi = prices[i];
        }else{
            dp[i] = prices[i]-mi;
        }
        ans = Math.max(ans,dp[i]);
    }
    return ans;

}