做网站必须要有数据库上海建设工程咨询有限公司
代码随想录训练营第49天|121.买卖股票的最佳时机，122.买卖股票的最佳时机II
- 121.买卖股票的最佳时机
- 文章
- 思路
- 代码
- 122.买卖股票的最佳时机II
- 文章
- 思路
- 代码
- 总结
121.买卖股票的最佳时机
文章
代码随想录|0121.买卖股票的最佳时机
思路
维护一个历史最低价，维护一个最低价基础上的最大收益
代码
class Solution {public int maxProfit(int[] prices) {int i, n;n = prices.length;int lowest = 0x7fffffff;int res = 0;for (i = 0; i < n; ++i) {lowest = lowest < prices[i] ? lowest : prices[i];res = res > prices[i] - lowest ? res : prices[i] - lowest;}return res;}
}
122.买卖股票的最佳时机II
文章
代码随想录|0122.买卖股票的最佳时机II（动态规划）
思路
dp[i]表示截止到第i天能获得的最大收益
d p [ i ] = M a t h . m a x ( d p [ i − 1 ] , d p [ i − 1 ] + p r i c e s [ i ] − p r i c e s [ i − 1 ] ) dp[i]=Math.max(dp[i-1], dp[i-1]+prices[i]-prices[i-1]) dp[i]=Math.max(dp[i−1],dp[i−1]+prices[i]−prices[i−1])
代码
class Solution {public int maxProfit(int[] prices) {int i, j, n;n = prices.length;int[] dp = new int[n];for (i = 1; i < n; ++i) {dp[i] = prices[i] > prices[i - 1] ? dp[i - 1] + prices[i] - prices[i - 1] : dp[i - 1];}return dp[n - 1];}
}
总结
感觉我的思路不太像卡哥的dp
II这个题以前是滑动窗口+贪心就很好理解
卡哥用的是考虑每天是否持有股票的两种情况来dp，反而耗时比我的长