算法-买卖股票的最佳时机
01、题目分析给定一个数组 prices ，它的第 i 个元素 prices 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。如果你不能获取任何利润，返回 0 。【leetcode】
示例1
输入:
输出: 5解释：在第3天(股票价格 = 2)的时候买入，在第6天(股票价格 = 7)的时候卖出，最大利润 = 7-2 = 5 ，不能选择在第2天买入，第3天卖出，这样就亏损7了；同时，你也不能在买入前卖出股票。
02、题解分析
方法1
分别计算不同时间买入和卖出的利润，然后不断更新，结束时就能找到利润的最大值
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pbWcyMDIyLmNuYmxvZ3MuY29tL2Jsb2cvMjM3NjE1Ni8yMDIyMDcvMjM3NjE1Ni0yMDIyMDcyOTE0MDY1NjE5My0xMDA4MjYyNTkucG5n
方法2
采用动态规划的方法【参考《团灭 LeetCode 股票买卖问题》】
对于动态规划方法，我们具体到每一天，看看总共有几种可能的「状态」，再找出每个「状态」对应的「选择」。我们要穷举所有「状态」，穷举的目的是根据对应的「选择」更新状态。
dp = max(dp, dp + prices);
解释：今天我没有股票，有两种可能：
要么是我昨天就没有，然后今天选择无操作，所以我今天还是没有持有 【dp】
要么是我昨天持有股票，但是今天我卖出了，所以我今天没有持有股票了 【dp + prices】
dp = max(dp, -prices);
解释：今天我持有股票，有两种可能：
要么我昨天就持有着股票，然后今天选择无操作，所以我今天还持有着股票【dp】
要么我昨天本没有持有，今天买入股票 【-prices】由递推公式 dp = max(dp, -prices); 和 dp = max(dp, prices + dp);可以看出其基础都是要从dp和dp推导出来。
那么dp表示第0天没有股票，不持有股票那么现金就是0，所以dp = 0;
dp表示第0天不持有股票，此时的持有股票就一定是买入股票了，因为不可能有前一天推出来，所以dp -= prices;
方法3
因为股票就买卖一次，那么贪心的想法很自然就是取最左最小值，然后依次用右边的值减去最小值，然后更新结果【参考代码随想录】
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pbWcyMDIyLmNuYmxvZ3MuY29tL2Jsb2cvMjM3NjE1Ni8yMDIyMDcvMjM3NjE1Ni0yMDIyMDcyOTE0NTMzNDMyNi0yMTAxMTc2NDM2LnBuZw==
03、题解
方法1
// 方法1int maxProfit(int prices[],int len) {if (len < 2) { return 0 ;}int ans=0;for(int i=0; i
页:
[1]