题目描述（简单难度）

和 一样，给定一个数组，代表每天的价格。区别在于 题只能进行一次买入卖出。但是这道题可以不停的买入、卖出，但是只有卖出了才能继续买入。

解法一

就用最简单的思想，我们穿越回去了过去，知道了未来每天的股票价格，要怎么操作呢？

跌了的前一天卖出，例如下边的例子

需要考虑两种特殊情况

一直上涨，没有下跌

  1. 1 3 5 9
  3. 那么我们在最后一天卖出就可以

考虑了上边的所有情况，就可以写代码了。

  1. public int maxProfit(int[] prices) {
  2.     int profit = 0;
  3.     int buy = 0;
  4.     int sell = 1;
  6.     for (; sell < prices.length; sell++) {
  7.         if (prices[sell] < prices[sell - 1]) {
  9.             if (sell != 1) {
  10.                 profit += prices[sell - 1] - prices[buy];
  11.             }
  12.             //下跌当天再次买入
  13.             buy = sell;
  15.         //到最后一天是上涨，那就在最后一天卖出
  16.         } else if (sell == prices.length - 1) {
  17.             profit += prices[sell] - prices[buy];
  18.         }
  20. }

还有一种持续下跌的情况

解法二

其实不用考虑那么多，再直接点，只要当前天相对于前一天上涨了，我们就前一天买入，当前天卖出。

  1. public int maxProfit(int[] prices) {
  2.     int profit = 0;
  3.     for (int i = 1; i < prices.length; i++) {
  4.         int sub = prices[i] - prices[i - 1];
  5.         if (sub > 0) {
  6.             profit += sub;
  7.         }
  8.     }
  9.     return profit;
  10. }

总

上边两种解法都是从实际情况出发，来考虑怎么盈利最大。 给出的理解方式也很好，这里分享一下。

解法一，其实每次就是找了波谷和波峰做了差，然后把所有的差进行累计。

解法二，找的是上升的折线段，把所有上升的折线段的高度进行了累计。

所以一些题，可能代码是一样的，但是理解的含义并不相同。

windliang wechat

添加好友一起进步~

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情