买卖股票的最佳时机

分析：本题考察的数据结构是数组，算法是dp。当然dp 的递推规律是要我们去找出来的。首先要明白，dp 一定是有一层关系在：下一个数的结果产生一定是与上一个数有关的。整个数组一开始可能这个关系不明显，也就是说这个关系很可能不是连续的，是一种跳跃式的递推关系。接下来我们的操作步骤:
1 去发现局部连续的递推关系，比如构造数组 1，2，3，7，8 ，很明显的是后面的数组元素的结果都是可以由前面的数产生关系的。
2 去找到跳跃的逻辑，根据什么跳跃。

于是我们发现，只要是前面一个数产生了一个最大值，下一个数要是比前一个数大，那么下一个数的最大值就可以利用前面的数的结果轻易生成。所以前面的数不仅要记录最大值，还要记录一下方便下一个数计算最大值的其他信息，这个其他信息就是最大值的起点。只要前一个数记录了起点，下一个数比前一个数大，那么用下一个数减去前一个数的最大值起点，就获得了下一个数的最大值，这样局部递推的关系我们就找到了。

对于跳跃的条件也就变成了我们要计算下一个数的最大值，根据前面的分析，我们只要找到前一个比它小的数就好了，因为那里记载了比它小的数生成最大值的起点。
结论：
1 递推关系就是下一个数生成的最大值等于下一个数减去往前一个数的起点。
2 跳跃的逻辑就是找第一个比它小的数

public int maxProfit (int[] prices) {
        // write code here
        if(prices==null || prices.length<2){
            return 0;
        }
        int res=Integer.MIN_VALUE;
        int [] tmp=new int [prices.length]; //用来存起点的数，可以存数也可以存索引，直接存数一步到位
        for(int i=0;i<tmp.length;i++){
            int preFirstMin=getPreFirstMin(prices,tmp,i);
            tmp[i]=preFirstMin;//把起点记下来
            res=prices[i]-tmp[i]>res?prices[i]-tmp[i]:res;//迭代更新最大值，可以用 dp数组存，但是这里只要个最大值，没必要
        }
        if(res<0){//这是个 trick ，测试用例里面的，，，，要是算出来收益最大都是负数，不买就永不会亏，，收益最大，题目种没说明还可以不买，，，这谁记得住还有这一遭
            res=0;
        }
        return res;
    }

    public int getPreFirstMin(int [] arr,int [] tmp,int index){ //找前一个比它小的数
        int res=0;
        for(int i=index-1;i>=0;i--){
            if(arr[i]<arr[index]){//找到第一个小的
                res=tmp[i];
                break;
            }
            if(i==0){//找不到的话最小就是它自己
                if(arr[index]<arr[i]){
                    res=arr[index];
                }
            }
        }
        return res;
    }