121. 买卖股票的最佳时机

  • 最多只允许完成一笔交易

  • 保存前面的最小值

    1. class Solution {
    2.   public int maxProfit(int[] prices) {
    3.       int minPrice = Integer.MAX_VALUE;
    4.       int res = 0;
    5.       for(int price : prices){
    6.           minPrice = Math.min(minPrice, price);
    7.           res = Math.max(res, price - minPrice);
    8.       }
    9.       return res;
    10.   }
    11. }

    122. 买卖股票的最佳时机 II

  • 可以尽可能地完成更多的交易

  • 交易的分解
  • 如果相隔的两天交易差值是正数，表示有收益则交易，如果是负数，则不交易，res+=0即可
  • res += Math.max(0, prices[i + 1] - prices[i]);

  • 截屏2021-01-03 上午9.00.48.png

    1. class Solution {
    2.   public int maxProfit(int[] prices) {
    3.       int res = 0;
    4.       for(int i = 0; i + 1 < prices.length; i++){
    5.           res += Math.max(0, prices[i + 1] - prices[i]);
    6.       }
    7.       return res;
    8.   }
    9. }

    123. 买卖股票的最佳时机 III

  • 最多可以完成 两笔 交易

  • 前后缀分解
    • 枚举第二次交易买入的时间，比如第i天
    • 第一次交易[0, i - 1]，第二次交易[i,n）两次交易完全独立，分别求出最大即可
    • 后面一段求最大：用第一题的做法，第i天买的，记录下i+1～n-1中的最大值