题解 | #股票(无限次交易)#
股票(无限次交易)
http://www.nowcoder.com/practice/9e5e3c2603064829b0a0bbfca10594e9
题意:
- 给定一个数组代某一股票价格,不限股票交易次数,不计算手续费,求最多可以赚多少钱。
方法一:贪心
解题思路:
- 由于是无限次数交易,因此贪心的策略是:如果后一天的价格高于前一天,就应当加上该差价;否则不变。
- 代码:设置last为前一天的价格,起始值为101,因此股票价格范围是[1,100],ans为最大收益,初始值为0;遍历数组prices,如果当前值x大于last,则把x-last加到ans中,更新last。最终得到的ans即为最大收益。
图解如下:
- 输入数据:[2,3,5,1,4,2,8]
- 对于最大收益,如下图折线图所示,每逢折线上升(红色线段)买进卖出即可,遇价格下降不操作。最大收益为:
(3-2)+(5-3)+(4-1)+(8-2)=1+2+3+6=12。
代码如下:
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * 计算最大收益 * @param prices int整型vector 股票每一天的价格 * @return int整型 */ int maxProfit(vector<int>& prices) { // write code here //设置起始值 int last=101,ans=0; //遍历,更新ans和last for(int x:prices){ if(x>last) ans+=x-last; last=x; } return ans; } };
复杂度分析:
时间复杂度:,遍历数组prices。
空间复杂度:,常数个临时变量。
方法二:动态规划
解题思路:
可以使用dp[i][0],dp[i][1]两个数组分别表示第i天持有股票所得最多现金和第i天不持有股票所得最多现金。
那么有如下递推式:
(1)dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]);
(2)dp[i][1]=max(dp[i-1][1],dp[i-1][1]+prices[i]);
- 递推式的含义也较好理解,对式(1):dp[i][0]来源于前一天的状态,即dp[i-1][0]和dp[i-1][1],前一天持股票今天不卖,以及前一天不持股票今天买进,选择两者最大值即可。同理dp[i][1]也是来源于前一天状态。
代码如下:
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * 计算最大收益 * @param prices int整型vector 股票每一天的价格 * @return int整型 */ int maxProfit(vector<int>& prices) { // write code here int n=prices.size(); //分配n*2的矩阵 vector<vector<int>> dp(n,vector<int>(2,0)); dp[0][0]=0-prices[0];//第0天持股最大收益 dp[0][1]=0;//第0天不持股最大收益 for(int i=1;i<n;i++){ dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]);//第i天持股最大收益 dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]);//第i天不持股最大收益 } return dp[n-1][1]; } };
复杂度分析:
时间复杂度:,n为天数,遍历数组dp。
空间复杂度:,额外的数组空间dp;