121. 买卖股票的最佳时机

image.png

暴力解法（超时）

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

贪心

  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  3.         //贪心
  4.         //取左侧的最小值
  5.         int low = Integer.MAX_VALUE;
  6.         int res = 0;
  8.         for(int i = 0 ; i < prices.length; i++ ) {
  9.             low = Math.min(low,prices[i]);
  10.             res = Math.max(res, prices[i] - low);
  11.         }
  13.         return res;
  15.     }
  16. }

动态规划

  1. class Solution {
  3.     public int maxProfit(int[] prices) {
  5.         int size = prices.length;
  7.         //dp[i][0] 代表第i天持有股票的最大收益
  8.         //dp[i][1] 代表第i天不持有股票的最大收益
  9.         int [][] dp = new int[size][2];
  10.         dp[0][0] = -prices[0];
  11.         dp[0][1] = 0;
  13.         for(int i = 1 ; i < size ; i++ ) {
  14.             dp[i][0] = Math.max(dp[i - 1][0], - prices[i]);
  16.             dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][0] + prices[i]);
  17.         }
  19.         return dp[size - 1][1];
  20.     }
  21. }

动态规划（滚动数组）

  1. class Solution {
  2.     public int maxProfit(int[] prices) {
  4.         // 求a除以2的n次方的余数 等价于 a & (2的n次方 - 1)
  5.         int size = prices.length;
  7.         int [][] dp = new int[2][2];
  9.         //持有股票
  10.         dp[0][0] = -prices[0];
  11.         //不持有股票
  12.         dp[0][1] = 0;
  14.         for(int i = 1 ; i < size ; i++) {
  15.             //dp[i % 2][0] = Math.max(dp[ (i - 1) % 2][0], -prices[i]);
  17.             dp[i & 1][0] = Math.max(dp[ (i - 1)  & 1][0], -prices[i]);
  20.             //dp [i % 2][1] = Math.max( dp[ (i - 1) % 2][1],dp[ (i - 1) % 2 ][0] + prices[i]);
  22.             dp [i & 1][1] = Math.max( dp[ (i - 1) & 1][1],dp[ (i - 1) & 1 ][0] + prices[i]);
  23.         }
  25.         return dp[ (size - 1) & 1][1];
  27.     }
  28. }