买卖股票交易（只交易一次）

思路：遍历数组找到当前交易额和目前最小交易额差价的最大一次交易

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

买卖股票（交易多次）

总的交易额 = 多次上升交易额差价之和

  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.       if(prices.length<=1) return 0;
  4.       int maxP=0;
  5.       int curPrice = prices[0];
  6.       for(int i=1;i<prices.length;i++){
  7.           if(curPrice<prices[i]){
  8.               maxP += (prices[i]-curPrice);
  9.           }
  10.           curPrice = prices[i];
  11.       }
  12.       return maxP;
  13.     }
  14. }

买卖股票（交易两次）

采用动态规划
分析如下：
初始状态 ——>保持不动——> 初始状态
初始状态 ——>第一次买人 ——> 买入1状态
买入1状态 ——> 保持不动
买入1状态——> 卖出 ——> 卖出1状态
卖出1状态 ——> 买入 ——> 买入2状态
卖出1状态 ——> 保持不动
卖出1状态 ——> 买入 ——> 买入2状态
买入2状态 ——> 保持不动
买入2状态 ——> 卖出 ——> 交易完成
dp[i][0][0] 原始状态 压缩状态 dp[i][0] 继续压缩状态 dp0
dp[i][1][1] 第一次买入 dp[i][1] dp1
dp[i][1][0] 第一次卖出 dp[i][2] dp2
dp[i][2][1] 第二次买入 dp[i][3] dp3
dp[i][2][0] 第二次卖出 dp[i][4] dp4

  1. class Solution {
  2.     //未状态压缩
  3.     // public int maxProfit(int[] prices) {
  4.     //    int n = prices.length;
  5.     //    int dp[][][] = new int [n][3][2];
  6.     //    dp[0][0][0] = 0;
  7.     //    dp[0][1][1] = -prices[0];
  8.     //    dp[0][1][0] =0;
  9.     //    dp[0][2][1] =-prices[0];
  10.     //    dp[0][2][0]=0;
  11.     //    for(int i=1;i<n;i++){
  12.          // 初始状态保持不动
  13.     //        dp[i][0][0] = dp[i-1][0][0];
  14.         // 第一次买入
  15.     //        dp[i][1][1] = Math.max(dp[i-1][1][1],dp[i][0][0]-prices[i]);
  16.        // 第一次卖出 
  17.     //        dp[i][1][0] = Math.max(dp[i-1][1][0],dp[i][1][1]+prices[i]);
  18.        // 第二次买入
  19.     //        dp[i][2][1] = Math.max(dp[i-1][2][1],dp[i][1][0]-prices[i]);
  20.         // 第二次卖出
  21.     //        dp[i][2][0] = Math.max(dp[i-1][2][0],dp[i][2][1]+prices[i]);
  22.     //    }
  23.     //    int a = Math.max(dp[n-1][0][0],dp[n-1][1][1]);
  24.     //    int b = Math.max(dp[n-1][1][0],dp[n-1][2][1]);
  25.     //    return Math.max(dp[n-1][2][0],Math.max(a,b));
  26.     // }
  27.     //状态压缩1
  28.     //  public int maxProfit(int[] prices) {
  29.     //      int n = prices.length;
  30.     //      int dp [][] = new int [n][5];
  31.     //      dp[0][0] = 0;
  32.     //      dp[0][1] = -prices[0];
  33.     //      dp[0][2] =0;
  34.     //      dp[0][3] =-prices[0];
  35.     //      dp[0][4] = 0;
  36.     //      for(int i=1;i<n;i++){
  37.     //          dp[i][0] = dp[i-1][0];
  38.     //          dp[i][1] = Math.max(dp[i-1][1],dp[i][0]-prices[i]);
  39.     //          dp[i][2] = Math.max(dp[i-1][2],dp[i][1]+prices[i]);
  40.     //          dp[i][3] = Math.max(dp[i-1][3],dp[i][2]-prices[i]);
  41.     //          dp[i][4] = Math.max(dp[i-1][4],dp[i][3]+prices[i]);
  42.     //      }
  43.     //      int a = Math.max(dp[n-1][0],dp[n-1][1]);
  44.     //      int b = Math.max(dp[n-1][2],dp[n-1][3]);
  45.     //      return Math.max(Math.max(a,b),dp[n-1][4]);
  46.     //  }
  47.      //状态压缩2
  48.     //   public int maxProfit(int[] prices) {
  49.     //       int dp0= 0;
  50.     //       int dp1= -prices[0];
  51.     //       int dp2 =0;
  52.     //       int dp3=-prices[0];
  53.     //       int dp4 =0;
  54.     //       for(int i=0;i<prices.length;i++){
  55.     //           dp1 = Math.max(dp1,dp0-prices[i]);
  56.     //           dp2 = Math.max(dp2,dp1+prices[i]);
  57.     //           dp3 = Math.max(dp3,dp2-prices[i]);
  58.     //           dp4 = Math.max(dp4,dp3+prices[i]);
  59.     //       }
  60.     //       int a = Math.max(dp0,dp1);
  61.     //       int b = Math.max(dp2,dp3);
  62.     //       return Math.max(Math.max(a,b),dp4);
  64.     //   }
  65.       采用递归来处理（深度搜索去递归状态树）
  66.       public int maxProfit(int[] prices) {
  67.           return dfs(prices,0,0,0);
  68.       }
  69.       index 表示当前交易的日期，status表示当前是买入或者卖出 表示交易的次数
  70.       private int dfs(int[]prices,int index,int status,int k){
  71.           //递归结束条件
  72.           if(index==prices.length || k==2){
  73.               return 0;
  74.           }
  75.           //a表示保持不动，b表示卖出，c表示买入
  76.           int a=0,b=0,c=0;
  77.           a= dfs(prices,index+1,status,k);
  78.           if(status==1){
  79.               b = dfs(prices,index,0,k+1)+prices[index];
  80.           }else{
  81.               c= dfs(prices,index,1,k)-prices[index];
  82.           }
  83.           return Math.max(Math.max(a,b),c);
  84.       }
  86. }

买卖股票（交易多次）

思路：如果此时k>=n/2,n为数组长度，则就可以转化为多次交易，否则采用动态规划求解