当前位置:首页>股市> 正文内容

【每日一题】给定一个整数数组prices(给定一个正整数数组)

3年前(2021-06-23)股市153
廊坊富士康招工

题目

给定一个整数数组 prices ,它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例1:

输入:k = 2, prices = [2,4,1]

输出:2

解释:在第 1 天 (股票价格 = 2) 的时候买入,在第 2 天 (股票价格 = 4) 的时候卖出,这笔交易所能获得的利润 = 4-2 = 2 。

示例2:

输入:k = 2, prices = [3,2,6,5,0,3]

输出:7

解释:在第 2 天 (股票价格 = 2) 的时候买入,在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得的利润 = 6-2 = 4 。

随后,在第 5 天 (股票价格 = 0) 的时候买入,在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3

思路

对于这种什么时候该做什么决策可以获得最大值的问题,我们都可以用动态规划解决,首先看下我们初始状态有哪些维度

(1)当前是第几天,我们用index表示当前是交易的第几天

(2)当前是持有股票还是不持有股票,我们用status来代表持股状态,status=0代表不持有股票,status=1代表持有股票

(3)当前已经完成了几次交易,我们用count表示当前已经完成了几次交易

(4)当前的利润是多少,我们用profit表示

ok,现在有了这些状态之后是我们该如何做决策的时候了,那目前我们假设处于index天,当前持有股票的状态是status,当前已经完成了count次交易,当前的利润是profit,那么我们可以做的选择有哪些呢?

(1)如果status=0 也就是说我们不持有股票,那我们可以做的操作有两种,第一 我们可以选择买入股票,重新计算profit,profit=profit-prices[index],此时交易次数count不变,因为一次买入和一次卖出才算一次交易,status需要变成持有股票status=1,第二 我们可以选择不买也不卖,就是原地不动等待机会,那么这个时候这些状态都不会变化除了天数会+1

(2)如果status=1,也就是说我们持有股票,那么我们可以做的操作有两种,第一,我们可以选择卖出股票,此时profit=profit+prices[index],status=status-1,count=count+1;第二我们可以保持不动,除了index+1 其他的不变

好了,现在可以做的选择有上面四个情况,那么我们什么时候结束呢?

(1)count==k,代表目前已经完成了k次交易,我们需要停止

【每日一题】给定一个整数数组prices

(2)index=len(prices),代表此时已经过完了最后一天

这两个结束条件之后我们可以计算当前的profit跟最大的profit对比,保存最大的profit

算法

var maxProfitNum intfunc maxProfit(k int, prices []int) int {tmaxProfitNum = 0tDfsMaxProfit(0,0,0,k,prices,0)tturn maxProfitNum}func DfsMaxProfit(index int,status int,count int,k int,prices []int,profit int){t// 当前的状态如下t// index 当前是第几天t// status 当前状态是持有股票(可以卖出) 不持有股票(可以买入)t// count 当前已经完成了几次交易t// k 一共可以交易k次 prices 天数 profit 当前这种行为链条的利润tif count == k  index == len(prices) {ttif maxProfitNum< profit {tttmaxProfitNum = profittt}ttturnt}tif status ==0 {tt// 不持有股票的时候 可以选择买入ttDfsMaxProfit(index+1,1,count,k,prices,profit-prices[index])tt// 选择不动ttDfsMaxProfit(index+1,0,count,k,prices,profit)t}else{tt// 持有股票的时候tt// 选择卖出ttDfsMaxProfit(index+1,0,count+1,k,prices,profit+prices[index])tt// 选择不动ttDfsMaxProfit(index+1,1,count,k,prices,profit)t}}

观澜富士康普工我要聘

扫描二维码推送至手机访问。

版权声明:本文由网友投稿发布,本网站仅提供存储空间服务,如侵犯了您的权利请立即联系我们进行删除。

本文链接:http://www.25z.cn/gushi/4631.html