题目

image.png

思路

  • 贪心算法，一次遍历，只要今天价格小于明天价格就在今天买入然后明天卖出
  • DP动态规划，第i天只有两种状态，不持有或持有股票，当天不持有股票的状态可能来自昨天卖出或者昨天也不持有，同理，当天持有股票的状态可能来自昨天买入或者昨天也持有中，取最后一天的不持有股票状态就是问题的解

代码

  1.     public int maxProfit(int[] prices) {
  2.         if (prices.length == 0) return 0;
  3.         int profix = 0, prev = prices[0];
  4.         for (int i = 1; i < prices.length; i++) {
  5.             if (prices[i] > prev) {
  6.                 profix += prices[i] - prev;;
  7.                 prev = prices[i];
  8.             } else {
  9.                 prev = Math.min(prev, prices[i]);
  10.             }
  11.         }
  12.         return profix;
  13.     }

买卖股票的最佳时机 II