> 文档中心 > LeetCode121. 买卖股票的最佳时机

LeetCode121. 买卖股票的最佳时机


思路

思路一:就买卖一次股票,所以直接找出前后两个数的差值最大的利润。

解法一:暴力解法,超时

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

思路二:就从左边找到最小的,右边找到最大的,这两个的差就是最大利润。

解法二

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

思路三:动态规划

动规五部曲

1.定义dp数组

dp[i][0]:表示第i天持有股票所得的最多现金。

dp[i][1]:表示第i天不持有股票所得的最多现金。

2.递推公式

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

3.初始化

dp[0][0]:第0天持有的股票所得的最大现金应该为-prices[0]。因为第0天持有股票只能是买入的,所以为-prices[0];

dp[0][1]:为0

4.遍历顺序

由递推公式可以知道是正序遍历

5.打印dp数组

最后结果是dp[prices.length-1][0],dp[prices.length-1][1]取最大的。

代码

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][0]+prices[i],dp[i-1][1]); } return Math.max(dp[prices.length-1][0],dp[prices.length-1][1]);