动态规划.3（股票1）

动态规划的精髓就是递归，将一个复杂的问题，通过层层分解，回到比较简单的情况，然后递归往回处理；这道题在我看来并不能被归入动态规划….但是leetcode就是认为它是动态规划…那也没办法
这道题，赋予了我们全知全能的能力…实际上这道题并没有任何实际意义，因为没有人可以预测未来的股票走向….

题目

买卖股票；给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xn8fsh/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

分析

关于股票买卖的问题，如果允许多次交易，可以使用贪心算法，但是这次只允许进行一次交易，所以贪心算法失效了…还是回到了动态规划问题；
举个例子{7,1,5,3,4,6}数组，记作price，每一天的操作只有可能是买入或者卖出；
创建一个数组resultMoney，记录每天卖出可能产生的最大收益；

1. 如果第1天卖出，这种情况是不存在的…也没有收益；

【0】产生的最大收益是

1. 如果第2天卖出，那么第一天一定买入了，此时产生的收益将是price[1]-price[0]；如果这个值小于0，那么不产生任何收益，赔钱了；

【0，0】

1. 如果第3天卖出，那么此时就会产生两个情况，第一天买入或者第二天买入；此时的最大收益是前两天能产生的最大收益+第二天和第三天的差价；在这个例子中，第一天和第二天并不能产生任何收益….因此只需要计算第二天和第三天是否能够产生收益即可；很明显产生了收益；

【0，0，4】最大收益4块钱

1. 如果第4天卖出，那么此时存在两种 盈利情况 如果赚钱了，那么赚到的钱等于resultMoney[2]+(price[3]-price[4])；如果没有赚钱（第四天的股价高于第三天）那么前四天最多就能赚2块钱了….在这个例子中第四天卖出去虽然能产生收益（股价=1的时候买入，股价=4的时候卖出），但是第四天的价格和第三天的价格差是负数，这代表着不如第三天卖掉，因此并没有产生更大的收益；

【0，0，4，0】最大收益仍旧是4块钱

1. 如果第五天卖出，第四天和第五天的差价收益是能让你赚到钱的…但是此题只允许买卖一次，如果第五天卖掉，那么能产生的最大收益将从4变成3块钱， 这里突然出现了问题，局部的上涨并不一定保证整体的盈利最大

所以我们需要换个思路；更换一个例子{7，3，5，1，2，4，3，6}

1. 第一天，min=7，result=0；
2. 第二天，min=3，result=0；
3. 第三天，min=3，result=2；
4. 第四天，min=1，result=0；
5. 第五天，min=1，result=1；
6. 第六天，min=1，result=3；
7. 第七天，min=1，result=2；
8. 第八天，min=1，result=5；

在只允许买卖一次的情况下，我认为这道题实在不能被成为动态规划…获取被归为双指针问题更好

股票和偷东西的差异

偷东西问题是不会产生0收益的，毕竟贼不走空…但是我们炒股要讲究基本法…这道题里没有让你赔钱已经很关照炒股的人了…..
所以这道题，在进行递归的时候，需要时刻注意，前n天产生的最大收益是什么，这个最大收益只和买入&卖出的两天的价格相关，因为只允许买卖一次，如果没有限定买卖次数的话，贪心算法（本质上也是一个动态规划，类似于偷东西问题）是可以的；

代码

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length==0)
            return 0;
        int minPrice=prices[0];
        int result=0;
        for(int i=0;i<prices.length;i++)
        {
            if(prices[i]-minPrice>result)
                result=prices[i]-minPrice;
            if(prices[i]<minPrice)
                minPrice=prices[i];
        }
        return result;
    }
}