力扣小白刷题之122题买卖股票的最佳时机Ⅱ

题目描述

可以进行多次交易，多次交易之间不能交叉进行。（必须在再次购买前卖出之前的股票）

解题思路

思路是参考力扣的最优解，写在博客里只是为了自己的记录学习。

• 股票买卖策略
  1. 单独交易日： 设今天价格p₁，明天价格p₂，则今天买入明天卖出可赚取金额p₂ - p₁（负值代表亏损）。
  2. 连续上涨交易日： 设此上涨交易日股票价格分别为p₁,p₂，…,p_n，则第一天卖最后一天卖收益最大，即p_n - p₁；等价于每天都买卖，即p_n - p₁ = (p₂ - p₁) + (p₃ - p₂) + (p_n - p_n-1)。
  3. 连续下降交易日： 则不买买收益最大，即不亏钱。
• 算法流程
  1. 遍历整个股票交易日价格列表 prices，策略是所有上涨交易日都买卖(赚到所有利润)，所有下降交易日都不买卖(永不亏钱)。
  2. 从第 i 天(i >= 1)开始，与第 i - 1的股价进行比较如果股价有严格上升，就将升高的股价 tmp = prices[i] - prices[i -1] 计入总利润，否则直接跳过。（该算法仅可用于计算，但计算的过程并不是真正交易的过程，但可以用贪心算法计算题目要求的最大利润）
  3. 返回总利润。

贪心算法

求解最优化问题的算法通常需要经过一系列的步骤，在每个步骤都面临多种选择。对于许多最优化问题，使用动态规划算法来求最优解有些杀鸡用牛刀了，可以使用更简单、更高效的算法。贪心算法(greedy algorithm)就是这样的算法，它在每一步都做出当时看起来最佳的选择。也就是说，它总是做出局部最优的选择，寄希望这样的选择能导致全局最优解。
"贪心算法"在每一步总是做出在当前看来最好的选择。
因此，

1. “贪心算法”和“动态规划”、“回溯搜索”算法一样，完成一件事情，是分步决策的；
2. "贪心算法"在每一步总是做出在当前看来最好的选择。“最好”代表：
   1. 根据题目的意思，可能是最小，也可能是最大。
   2. 贪心算法和动态规划相比，它既不看前面(也就是说它不需要从前面的状态转移过来)，也不看后面(无后效性，后面的选择不会对前面的选择有影响)，因此贪心算法时间复杂度一般是线性的，空间复杂度是常数级别的。
   3. 这道题“贪心”的地方在于，对于“今天的股价 - 昨天的股价”，得到的结果有三种可能：正数、0、负数。
      贪心算法的决策是：只加正数

代码

时间复杂度： O(N)，N为股票数组长度，只需遍历一次
空间复杂度： O(1)