day48

1、leetcode121 买卖股票的最佳时机

1. 暴力破解，超时

   class Solution {
       public int maxProfit(int[] prices) {
           int res = 0;
           for(int i=0; i<prices.length; i++) {
               for(int j=i+1; j<prices.length; j++) {
                   res = Math.max(res, prices[j]-prices[i]);
               }
           }
           return res;
       }
   }
   

2. 贪心

   class Solution {
       public int maxProfit(int[] prices) {
           int low = Integer.MAX_VALUE;
           int res = 0;
   
           for(int i=0; i<prices.length; i++) {
               low = Math.min(low, prices[i]); //找到最低价格的股票购入点
               res = Math.max(res, prices[i]-low);
           }
   
           return res;
       }
   }
   

3. 动规

   1. 定义动规数组

      • dp[i] [0]: 第i天持有股票时的最大金额【持有，可以是当天买入，也可以是前几天就买入】
      • dp[i] [1]: 第i天不持有股票时的最大金额【前几天就卖了or当天才卖】

   2. 递归公式

      • dp[i] [0] = Math.max(dp[i-1] [0] , -price[i])
      • dp[i] [1] = Math.max(dp[i-1] [1] , price[i] + dp[i-1] [0] )

   3. 初始化

      • dp[0] [0] = -price[0]
      • dp[0] [1] = 0

   4. 遍历顺序

      • 从前向后

   5. 举例

   6. 代码

      class Solution {
          public int maxProfit(int[] prices) {
              int[][] dp = new int[prices.length][2];
              dp[0][0] = -prices[0];
              dp[0][1] = 0;
      
              for(int i=1; i<prices.length; i++) {
                  dp[i][0] = Math.max(dp[i-1][0], -prices[i]);
                  dp[i][1] = Math.max(dp[i-1][1], prices[i]+ dp[i-1][0]);
              }
      
              return dp[prices.length-1][1];
          }
      }
      

2、leetcode 买卖股票的最佳时机Ⅱ

1. 贪心

   1. 局部最优：收集每天的正利润，全局最优：求得最大利润。

   2. 代码

      class Solution {
          public int maxProfit(int[] prices) {
              int maxBenefit = 0;
              for(int i=1; i<prices.length; i++) {
                  maxBenefit += Math.max(prices[i]-prices[i-1], 0);//累加每一天的正利润
              }
              return maxBenefit;
          }
      }
      

2. 动规

   1. 定义动规数组

      • dp[i] [0]: 第i天持有股票时的最大金额
        • 之前买入 dp[i] [0] = dp[i-1] [0]
        • 当天买入
          • 之前卖了，当天买 dp[i] [0] = dp [i-1] [1] -prices[i]
          • 当天才卖，当天又买 dp[i] [0] = dp [i-1] [0] + prices[i] - prices[i] = dp [i-1] [0]
      • dp[i] [1]: 第i天不持有股票时的最大金额【前几天就卖了or当天才卖】
        • 之前卖了 dp[i] [1] = dp[i-1] [1]
        • 当天才卖 dp[i] [1] = dp[i-1] [0] + prices[i]

   2. 递归公式

      • dp[i] [0] = Math.max(dp[i-1] [0] ,dp [i-1] [1] -prices[i])
      • dp[i] [1] = Math.max(dp[i-1] [1] , price[i] + dp[i-1] [0] )

   3. 初始化

      • dp[0] [0] = -price[0]
      • dp[0] [1] = 0

   4. 遍历顺序

      • 从前向后

   5. 举例

   6. 代码

      class Solution {
          public int maxProfit(int[] prices) {
              int[][] dp = new int[prices.length][2];
              dp[0][0] = -prices[0];
              dp[0][1] = 0;
      
              for(int i=1; i<prices.length; i++) {
                  dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i]);
                  dp[i][1] = Math.max(dp[i-1][1], prices[i] + dp[i-1][0]);
              }
      
              return dp[prices.length-1][1];
          }
      }