网站建设 十年,wordpress 设置网站目录,php网站开发是什么,网站流量监控优质博文#xff1a;IT-BLOG-CN 一、题目
给你一个整数数组prices#xff0c;其中prices[i]表示某支股票第i天的价格。在每一天#xff0c;你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买#xff0c;然后在同一天出售。返回你能获得… 优质博文IT-BLOG-CN 一、题目
给你一个整数数组prices其中prices[i]表示某支股票第i天的价格。在每一天你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买然后在同一天出售。返回你能获得的最大利润。
示例 1 输入prices [7,1,5,3,6,4] 输出7 解释在第2天股票价格 1的时候买入在第3天股票价格 5的时候卖出, 这笔交易所能获得利润 5 - 1 4。随后在第 4 天股票价格 3的时候买入在第 5 天股票价格 6的时候卖出, 这笔交易所能获得利润 6 - 3 3 。 总利润为 4 3 7 。
示例 2 输入prices [1,2,3,4,5] 输出4 解释在第1天股票价格 1的时候买入在第5天 股票价格 5的时候卖出, 这笔交易所能获得利润 5 - 1 4。总利润为4。
示例 3 输入prices [7,6,4,3,1] 输出0 解释在这种情况下, 交易无法获得正利润所以不参与交易可以获得最大利润最大利润为0。 1 prices.length 3 * 104 0 prices[i] 104 二、代码
【1】动态规划 定义状态dp[i][0]表示第i天交易完后手里没有股票的最大利润dp[i][1]表示第i天交易完后手里持有一支股票的最大利润i从0开始。考虑dp[i][0]的转移方程如果这一天交易完后手里没有股票那么可能的转移状态为前一天已经没有股票即dp[i−1][0]或者前一天结束的时候手里持有一支股票即dp[i−1][1]这时候我们要将其卖出并获得prices[i]的收益。因此为了收益最大化我们列出如下的转移方程dp[i][0]max{dp[i−1][0],dp[i−1][1]prices[i]}再来考虑dp[i][1]按照同样的方式考虑转移状态那么可能的转移状态为前一天已经持有一支股票即dp[i−1][1]或者前一天结束时还没有股票即dp[i−1][0]这时候我们要将其买入并减少prices[i]的收益。可以列出如下的转移方程dp[i][1]max{dp[i−1][1],dp[i−1][0]−prices[i]}
对于初始状态根据状态定义我们可以知道第0天交易结束的时候dp[0][0]0dp[0][1]−prices
因此我们只要从前往后依次计算状态即可。由于全部交易结束后持有股票的收益一定低于不持有股票的收益因此这时候dp[n−1][0]的收益必然是大于dp[n−1][1]的最后的答案即为dp[n−1][0]。
class Solution {public int maxProfit(int[] prices) {if (prices.length 2) {return 0;}// 思路通过二维数组表示当前的两种状态 prices[i][0] 表示持有现金 prices[i][1]表示持有股票每次遍历获取Maxint[][] dp new int[prices.length][2];// 初始化0dp[0][0] 0;dp[0][1] -prices[0];for (int i 1; i prices.length; i) {dp[i][0] Math.max(dp[i-1][0], dp[i-1][1] prices[i]);dp[i][1] Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);}return dp[prices.length - 1][0];}
}注意到上面的状态转移方程中每一天的状态只与前一天的状态有关而与更早的状态都无关因此我们不必存储这些无关的状态只需要将dp[i−1][0]和dp[i−1][1]存放在两个变量中通过它们计算出dp[i][0]和dp[i][1]并存回对应的变量以便于第i1天的状态转移即可。
class Solution {public int maxProfit(int[] prices) {int n prices.length;int dp0 0, dp1 -prices[0];for (int i 1; i n; i) {int newDp0 Math.max(dp0, dp1 prices[i]);int newDp1 Math.max(dp1, dp0 - prices[i]);dp0 newDp0;dp1 newDp1;}return dp0;}
}时间复杂度 O(n)其中n为数组的长度。一共有2n个状态每次状态转移的时间复杂度为O(1)因此时间复杂度为O(2n)O(n)。 空间复杂度 O(n)我们需要开辟O(n)空间存储动态规划中的所有状态。如果使用空间优化空间复杂度可以优化至O(1)。
【2】贪心 由于股票的购买没有限制因此整个问题等价于寻找x个不相交的区间(li,ri]使得如下的等式最大化∑i1xa[ri]−a[li]其中li表示在第li天买入ri表示在第ri天卖出。同时我们注意到对于(li,ri]这一个区间贡献的价值a[ri]−a[li]其实等价于(li,li1],(li1,li2],…,(ri−1,ri]这若干个区间长度为1的区间的价值和即a[ri]−a[li](a[ri]−a[ri−1])(a[ri−1]−a[ri−2])…(a[li1]−a[li])因此问题可以简化为找x个长度为1的区间(li,li1]使得∑i1xa[li1]−a[li]价值最大化。
贪心的角度考虑我们每次选择贡献大于0的区间即能使得答案最大化因此最后答案为ans∑i1n−1max{0,a[i]−a[i−1]}其中n为数组的长度。需要说明的是贪心算法只能用于计算最大利润计算的过程并不是实际的交易过程。
考虑题目中的例子[1,2,3,4,5]数组的长度n5由于对所有的1≤in1都有a[i]a[i−1]因此答案为ans∑i1n−1a[i]−a[i−1]4但是实际的交易过程并不是进行4次买入和4次卖出而是在第1天买入第5天卖出。
class Solution {public int maxProfit(int[] prices) {int ans 0;int n prices.length;for (int i 1; i n; i) {ans Math.max(0, prices[i] - prices[i - 1]);}return ans;}
}时间复杂度 O(n)其中n为数组的长度。我们只需要遍历一次数组即可。 空间复杂度 O(1)只需要常数空间存放若干变量。
