网站建设前的功能,赣州人才网官方网站,手游源码网,给村里做网站题目
给定一个数组 prices #xff0c;它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票#xff0c;并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大…题目
给定一个数组 prices 它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润返回 0 。
示例 1
输入[7,1,5,3,6,4] 输出5 解释在第 2 天股票价格 1的时候买入在第 5 天股票价格 6的时候卖出最大利润 6-1 5 。注意利润不能是 7-1 6, 因为卖出价格需要大于买入价格同时你不能在买入前卖出股票。
示例 2
输入prices [7,6,4,3,1] 输出0 解释在这种情况下, 没有交易完成, 所以最大利润为 0。
提示
1 prices.length 1 0 5 10^5 1050 prices[i] 1 0 4 10^4 104
解题思路
先考虑最简单的「暴力遍历」即枚举出所有情况并从中选择最大利润。设数组 prices 的长度为 n 由于只能先买入后卖出因此第 1 天买可在未来 n−1 天卖出第 2 天买可在未来 n−2天卖出……以此类推共有 (n−1)(n−2)⋯0n(n-1)/2种情况时间复杂度为 O( N 2 N^2 N2) ) 。考虑到题目给定的长度范围 1≤prices.length≤ 1 0 5 10^5 105需要思考更优解法。
因为暴力法会产生许多冗余计算。例如若第 1 天价格低于第 2 天价格即第 1 天成本更低那么我们一定不会选择在第 2 天买入。进一步的若在前 i天选择买入若想达到最高利润则一定选择价格最低的交易日买入。考虑根据此贪心思想遍历价格列表 prices 并执行两步
由于初始值 i0 为了序号对应本文设从第 0 天开始
更新前 i天的最低价格即最低买入成本 cost更新前 i天的最高利润 profit 即选择「前 i−1天最高利润 profit 」和「第 i 天卖出的最高利润 price - cost 」中的最大值。
class Solution {public int maxProfit(int[] prices) {int cost Integer.MAX_VALUE, profit 0;for (int price : prices) {cost Math.min(cost, price);profit Math.max(profit, price - cost);}return profit;}
}复杂度分析
时间复杂度 O( N N N) 其中 N 为数组 prices 长度。遍历 prices 使用线性时间。空间复杂度 O( 1 1 1) 变量 cost , profit 使用 O( 1 1 1) 空间。
关于动态规划
动态规划Dynamic Programming简称 DP是一种在数学、计算机科学和经济学中使用的通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。动态规划方法的基本思想是将待求解的问题分解成若干个相互重叠的子问题求解一个子问题时将其解存储起来以便以后利用。这样在求解任何一个子问题时所利用的子问题的解都是已经计算过的从而避免了重复计算。
以下是动态规划的一些基本步骤
描述最优解的结构如果问题的最优解包含了其子问题的最优解则称该问题具有最优子结构性质。动态规划利用这一性质通过求解子问题的最优解来构造原问题的最优解。定义状态状态就是原问题和子问题的解。状态必须能够表示出与原问题相关的所有信息从而能够推导出子问题的解。状态转移方程状态转移方程就是描述状态之间关系的方程。它表示了如何从子问题的最优解推导出原问题的最优解。计算最优解按照状态转移方程从子问题的最优解开始逐步推导出原问题的最优解。
下面是一个经典的动态规划问题——背包问题的例子
给定一组物品每种物品都有自己的重量和价值。在限定的总重量内我们如何选择才能使得物品的总价值最高。这就是一个典型的背包问题。我们可以使用动态规划来解决这个问题。首先我们定义状态 dp[i][j] 表示在前 i 个物品中选择总重量不超过 j 的物品能够得到的最大价值。然后我们可以得到状态转移方程
如果第 i 个物品的重量大于 j那么 dp[i][j] dp[i-1][j]即前 i 个物品的最大价值等于前 i-1 个物品的最大价值因为第 i 个物品太重无法放入背包。否则dp[i][j] max(dp[i-1][j], dp[i-1][j-weight[i]] value[i])。这里有两种选择要么不选第 i 个物品此时最大价值为 dp[i-1][j]要么选择第 i 个物品此时最大价值为前 i-1 个物品在总重量不超过 j-weight[i] 的情况下的最大价值加上第 i 个物品的价值。
最后我们遍历所有状态计算出 dp[n][W]其中 n 是物品的数量W 是背包的总重量限制即为问题的解。
这只是动态规划的一个简单应用。实际上动态规划可以应用于各种领域如生物信息学、图像处理、机器学习等是解决复杂问题的一种强大工具。
