假设你有一个数组prices,长度为n,其中prices[i]是某只股票在第i天的价格,请根据这个价格数组,返回买卖股票能获得的最大收益
1. 你可以多次买卖该只股票,但是再次购买前必须卖出之前的股票
2. 如果不能获取收益,请返回0
3. 假设买入卖出均无手续费
数据范围: ,
要求:空间复杂度 ,时间复杂度
进阶:空间复杂度 ,时间复杂度
[8,9,2,5,4,7,1]
7
在第1天(股票价格=8)买入,第2天(股票价格=9)卖出,获利9-8=1 在第3天(股票价格=2)买入,第4天(股票价格=5)卖出,获利5-2=3 在第5天(股票价格=4)买入,第6天(股票价格=7)卖出,获利7-4=3 总获利1+3+3=7,返回7
[5,4,3,2,1]
0
由于每天股票都在跌,因此不进行任何交易最优。最大收益为0。
[1,2,3,4,5]
4
第一天买进,最后一天卖出最优。中间的当天买进当天卖出不影响最终结果。最大收益为4。
总天数不大于200000。保证股票每一天的价格在[1,100]范围内。
很容易想出这道题的状态转移方程
func MaxProfitBM81(prices []int) int { a, b := -prices[0], 0 for i := 2; i <= len(prices); i++ { a, b = Max(a, b-prices[i-1]), Max(b, a+prices[i-1]) } return b }
package main /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * 计算最大收益 * @param prices int整型一维数组 股票每一天的价格 * @return int整型 */ func maxProfit( prices []int ) int { // write code here cash := 0 stock := -prices[0] for i := 1; i < len(prices); i++ { pre_cash := cash pre_stock := stock cash = max(pre_cash, pre_stock + prices[i]) stock = max(pre_stock, pre_cash - prices[i]) } return cash } func max(a, b int) int { if a > b { return a } return b }
package main /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * 计算最大收益 * @param prices int整型一维数组 股票每一天的价格 * @return int整型 */ func maxProfit( prices []int ) int { dp:=make([][]int,len(prices)) for i,_:=range dp{ dp[i]=make([]int,2) } dp[0][0]=-prices[0] dp[0][1]=0 for i,price:=range prices{ if i==0{ continue } dp[i][0]=max(dp[i-1][1]-price,dp[i-1][0]) dp[i][1]=max(dp[i-1][0]+price,dp[i-1][1]) } return max(dp[len(dp)-1][0],dp[len(dp)-1][1]) } func max(a,b int)int{ if a>b{ return a } return b }
package main /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * 计算最大收益 * @param prices int整型一维数组 股票每一天的价格 * @return int整型 */ func maxProfit( prices []int ) int { // 动态规划 if len(prices) < 2 { return 0 } dp := make([][]int, len(prices)) for i, _ := range dp { dp[i] = []int{0, 0} } dp[0][0] = 0 dp[0][1] = -prices[0] for i:=1; i<len(prices); i++ { dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i]) dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i]) //和前一题不同 } return dp[len(prices)-1][0] } func max(x, y int) int { if x > y { return x } return y }