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

题意：

给定一个数组代某一股票价格，不限股票交易次数，不计算手续费，求最多可以赚多少钱。

方法一：贪心

解题思路：

由于是无限次数交易，因此贪心的策略是：如果后一天的价格高于前一天，就应当加上该差价；否则不变。
代码：设置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;
    }

};

复杂度分析：

时间复杂度： $O(n)$ ，遍历数组prices。
空间复杂度： $O(1)$ ，常数个临时变量。

方法二：动态规划

解题思路：

可以使用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];
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，n为天数，遍历数组dp。
空间复杂度： $O(n)$ ，额外 $O(n)$ 的数组空间dp；