代码随想录训练营第49天|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天能获得的最大收益
$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，反而耗时比我的长