一篇公众号文章

121.买卖股票的最佳时机（简单）

121.买卖股票的最佳时机（简单）
只能交易一次，老的思路：
dp[0][i] 第i天手中没有持有股票
dp[1][i] 第i天手中持有股票

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

一点优化,x1表示持有，x0表示没有持有

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

122.买卖股票的最佳时机 II（简单）

122.买卖股票的最佳时机 II（简单）
可以交易无限次

  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         if(prices==null||prices.length==0) return 0;
  4.         int x0=0;
  5.         int x1=-prices[0];
  6.         for(int i=1;i<prices.length;i++){
  7.             x0=Math.max(x0,x1+prices[i]);
  8.             x1=Math.max(x1,x0-prices[i]);
  9.         }
  10.         return x0;
  11.     }
  12. }

还可以用贪心算法

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

123.买卖股票的最佳时机 III（困难）

123.买卖股票的最佳时机 III（困难）
可以买卖最多两次
变量的名字的含义：x11已经买了1次手里有1只股票
注意循环里面的顺序
逻辑上肯定是
0（还没有买卖过）—>x11（第一次买）—>x10（第一次卖）
—>x21（第二次买）—>x20（第二次卖）
也可以设计成二位数组dp[1][1]这样

  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.       int len=prices.length;
  4.       if(len==0||len==1) return 0;
  5.       int x11=-prices[0];
  6.       int x10=Integer.MIN_VALUE;
  7.       int x21=Integer.MIN_VALUE;
  8.       int x20=Integer.MIN_VALUE;
  9.       for(int i=1;i<len;i++){
  10.         x11=Math.max(x11,-prices[i]);
  11.         x10=Math.max(x10,x11+prices[i]);
  12.         x21=Math.max(x21,x10-prices[i]);
  13.         x20=Math.max(x20,x21+prices[i]);
  14.       }
  15.       return x20;
  16.     }
  17. }

188.买卖股票的最佳时机 IV（困难）

188.买卖股票的最佳时机 IV（困难）
是上一个的进阶，可以买卖k次
首先需要看下k是否很大相当于允许无限次交易—->变成题目122

  1. class Solution {
  2.     public int maxProfit(int k, int[] prices) {
  3.       int len=prices.length;
  4.       if(len==0||len==1) return 0;
  5.       if(2*k>=len){
  6.         //unlimited sale
  7.         int x0=0,x1=-prices[0];
  8.         for(int i=1;i<len;i++){
  9.           x0=Math.max(x0,x1+prices[i]);
  10.           x1=Math.max(x1,x0-prices[i]);
  11.         }
  12.         return x0;
  13.       }else{
  14.         int[][] dp=new int[k+1][2];
  15.         for(int i=1;i<=k;i++){
  16.           if(i==1) dp[1][1]=-prices[0];
  17.           else dp[i][1]=Integer.MIN_VALUE;
  18.           dp[i][0]=Integer.MIN_VALUE;
  19.         }
  20.         for(int i=1;i<len;i++){
  21.           for(int j=1;j<=k;j++){
  22.             dp[j][1]=Math.max(dp[j][1],dp[j-1][0]-prices[i]);
  23.             dp[j][0]=Math.max(dp[j][0],dp[j][1]+prices[i]);
  24.           }
  25.         }
  26.         return dp[k][0];
  27.       }
  28.     }
  29. }

309.最佳买卖股票时机含冷冻期（中等）

309.最佳买卖股票时机含冷冻期（中等）
冷冻期相当于是隔一天才能买，所以买入的时候不能是x0-prices[i]，而是”上一次x0”-prices[i]，用x2来记录上一次x0

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

714.买卖股票的最佳时机含手续费（中等）

714.买卖股票的最佳时机含手续费（中等）

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