题解 | #股票(无限次交易)#

股票(无限次交易)

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;

全部评论

相关推荐

09-02 17:43
门头沟学院 C++
空๑۩۞۩๑白:学历硬伤,先多看看中厂拿个保底吧
点赞 评论 收藏
分享
牛客717484937号:双飞硕没实习挺要命的
点赞 评论 收藏
分享
10-25 14:25
门头沟学院 C++
投的服务端研发岗,基本上就只问了实习和简历,啥八股都没有,也没给算法题,然后就结束了
ngiv:你看看别人面经就知道了, 拼多多三面很多主管面, 基本上就是20分钟纯聊天, 当然也看到有问了一个小时的
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务