ToB企服应用市场:ToB评测及商务社交产业平台

标题: 算法-买卖股票的最佳时机 [打印本页]
作者: 石小疯    时间: 2022-9-3 20:46
标题: 算法-买卖股票的最佳时机
01、题目分析

给定一个数组 prices ，它的第 i 个元素 prices 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。如果你不能获取任何利润，返回 0 。【leetcode】
示例1
  1. 输入: [8,9,2,5,4,7,1]
  2. 输出: 5
复制代码
解释：在第3天(股票价格 = 2)的时候买入，在第6天(股票价格 = 7)的时候卖出，最大利润 = 7-2 = 5 ，不能选择在第2天买入，第3天卖出，这样就亏损7了；同时，你也不能在买入前卖出股票。
02、题解分析

方法1

分别计算不同时间买入和卖出的利润，然后不断更新，结束时就能找到利润的最大值

方法2

采用动态规划的方法【参考《团灭 LeetCode 股票买卖问题》】
对于动态规划方法，我们具体到每一天，看看总共有几种可能的「状态」，再找出每个「状态」对应的「选择」。我们要穷举所有「状态」，穷举的目的是根据对应的「选择」更新状态。
  1. dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
  2. 解释：今天我没有股票，有两种可能：
  3.       要么是我昨天就没有，然后今天选择无操作，所以我今天还是没有持有      【dp[i-1][0]】
  4.       要么是我昨天持有股票，但是今天我卖出了，所以我今天没有持有股票了    【dp[i-1][1] + prices[i]】
  5. dp[i][1] = max(dp[i-1][1], -prices[i]);
  6. 解释：今天我持有股票，有两种可能：
  7.       要么我昨天就持有着股票，然后今天选择无操作，所以我今天还持有着股票  【dp[i-1][1]】
  8.       要么我昨天本没有持有，今天买入股票                               【-prices[i]】
复制代码
由递推公式 dp[0] = max(dp[i - 1][0], -prices); 和 dp[1] = max(dp[i - 1][1], prices + dp[i - 1][0]);可以看出其基础都是要从dp[0][0]和dp[0][1]推导出来。
那么dp[0][0]表示第0天没有股票，不持有股票那么现金就是0，所以dp[0][0] = 0;
dp[0][1]表示第0天不持有股票，此时的持有股票就一定是买入股票了，因为不可能有前一天推出来，所以dp[0][0] -= prices[0];
方法3

因为股票就买卖一次，那么贪心的想法很自然就是取最左最小值，然后依次用右边的值减去最小值，然后更新结果【参考代码随想录】

03、题解

方法1

[code]// 方法1int maxProfit(int prices[],int len) {  if (len < 2) {    return 0 ;  }  int ans=0;  for(int i=0; i



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4