leetcode121 best time buy and sell stock

意思就是说在一组数字里，找到后出现的数减前面数的最大差值。

考虑两种情况：

1. 数组内的数不足两位或为空，则返回0

2. 数组内数大于2，就是我们要考虑的动态规划问题了

建立一个动态数组，用于存储0~下标天内的最大差值

一个临时数minprice记录0~i下标天内出现的最小数

class Solution {

    public int maxProfit(int[] prices) {
        if(prices == null || prices.length < 2)    return 0;
        int[] dp = new int[prices.length];
        int minprice = prices[0];
        for(int i = 1 ;  i < prices.length ; i++){
            minprice = (minprice<prices[i]) ? minprice : prices[i];
            dp[i] = Math.max(dp[i-1],prices[i]-minprice);
        }
        return dp[dp.length-1];
    }
}

有一种更省空间的写法，不使用动态数组存储最大收益了，直接使用一个int整数即可，不过这对时间复杂度没什么影响。。

class Solution {
    public int maxProfit(int[] prices) {
        if(prices == null || prices.length < 2)    return 0;
        // int[] dp = new int[prices.length];
        int maxprofit = 0;
        int minprice = prices[0];
        for(int i = 1 ;  i < prices.length ; i++){
            minprice = (minprice<prices[i]) ? minprice : prices[i];
            maxprofit = Math.max(maxprofit,prices[i]-minprice);
        }
        return maxprofit;
    }
}

试下来会发现每个动态规划的问题都可以用降一维的方法处理哦~一维转数字可能看不出来，但二维转一维就可以省很多空间了