题目描述

image.png

解题思路

贪心法

本题贪心就是计算每天的利润，将所有正利润相加便是最大利润，来源就是每个股票只可以买一个，且没有卖出时不能再买，而且股票利润可以拆分。
如果想到其实最终利润是可以分解的，那么本题就很容易了！
如何分解呢？
假如第0天买入，第3天卖出，那么利润为：prices[3] - prices[0]。
相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。
此时就是把利润分解为每天为单位的维度，而不是从0天到第3天整体去考虑！
那么根据prices可以得到每天的利润序列：(prices[i] - prices[i - 1])…..(prices[1] - prices[0])。
image.png
从图中可以发现，其实我们需要收集每天的正利润就可以，收集正利润的区间，就是股票买卖的区间，而我们只需要关注最终利润，不需要记录区间。
那么只收集正利润就是贪心所贪的地方！
局部最优：收集每天的正利润，全局最优：求得最大利润。

  1. /**
  2.          * 贪心算法
  3.          *
  4.          * @param prices
  5.          * @return
  6.          */
  7. public int maxProfit(int[] prices) {
  8.     int result = 0;
  9.     for (int i = 1; i < prices.length; i++) {
  10.         int profits = prices[i] - prices[i - 1];
  11.         // 贪心贪的地方：只计算利润为正的两张股票
  12.         if (profits > 0) {
  13.             result += profits;
  14.         }
  15.     }
  16.     return result;
  17. }

动态规划

见动态规划