力扣121题: 买卖股票的最佳时机
【题目描述】
给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0
【题目链接】. - 力扣(LeetCode)
【解题代码】
public class MaxProfit {
public static void main(String[] args) {
//int[] prices = {7, 1, 5, 3, 6, 4};
int[] prices = {7, 6, 4, 3, 1};
System.out.println("The result is: " + new MaxProfit().maxProfit(prices));
}
public int maxProfit(int[] prices) {
// 定义动态规划中间过程数组
int dp[] = new int[prices.length];
// 初始化历史最低股价
int minPrice = prices[0];
// 初始化历史最大收益
int maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
// 当天最大收益等于当前股价减去初始化历史最低股价
dp[i] = prices[i] - minPrice;
// 当天股价如果低于历史最低股价,更新历史最新股价
minPrice = Math.min(minPrice, prices[i]);
// 保存到当天为止,最大的收益
maxProfit = Math.max(maxProfit, dp[i]);
}
return maxProfit;
}
}
【解题步骤】
- 从题目描述可以得知,此问题是要根据历史依次往后计算当天的最大股票收益值,很自然的想到采用动态规划的算法,因此照例定义一个动态规划数组
// 定义动态规划中间过程数组 int dp[] = new int[prices.length];
- 再次根据题目可知,当天收益等于当天的股价减去历史最低股价。然后依次保存最大的收益即可,因此需要定义历史最低股价和历史最大收益两个变量
// 初始化历史最低股价 int minPrice = prices[0]; // 初始化历史最大收益 int maxProfit = 0;
- 接下来就是按照动态规划的算法,依次计算中间过程,并不断更新历史最低股价和历史最大收益即可
// 依次计算每天的最大收益 for (int i = 1; i < prices.length; i++) { // 当天最大收益等于当前股价减去初始化历史最低股价 dp[i] = prices[i] - minPrice; // 当天股价如果低于历史最低股价,更新历史最新股价 minPrice = Math.min(minPrice, prices[i]); // 保存到当天为止,最大的收益 maxProfit = Math.max(maxProfit, dp[i]); }
- 最后返回最大收益值即可
return maxProfit;
【思路总结】
- 动态规划算法是数据结构中一个很重要的算法,另外一般学校里教的都很浅薄,程序员一定要自学掌握其算法脉络,并能学会灵活运用;
- 动态规划数组的做法一般都是定义个一维或者二维数据,依次递推计算当前数值;
- 无后效性,递推算法一般只需要考虑眼前最近一层,其它层一定不需要考虑。“未来与过去无关”
原文地址:https://blog.csdn.net/IT_Fly/article/details/136361394
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!