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]);