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

题目：股票无限次交易

描述：假定你知道某只股票每一天价格的变动。

你最多可以同时持有一只股票。但你可以无限次的交易（买进和卖出均无手续费）。

请设计一个函数，计算你所能获得的最大收益。

示例1：输入：[5,4,3,2,1]，返回值：0

说明：由于每天股票都在跌，因此不进行任何交易最优。最大收益为0。

示例2：输入：[1,2,3,4,5]，返回值：4

说明：第一天买进，最后一天卖出最优。中间的当天买进当天卖出不影响最终结果。最大收益为4。

解法一：

思路分析：通过题目分析，我们可以很清楚的想到这是一个数学问题，凡是涉及数学问题，都可以采用暴力法进行分析，所以我们采用暴力法进行研究，首先设定一个指针变量i，因为股票是两两之间的连续变化，题目要求取得最大收益，所以可以设定最大值为sum，当第二天的价钱大于第一天的价钱，就将第二天的减去第一天的，即为收益，通过不断的循环来计算出最大收益即可。

实例分析：输入：[5,4,3,2,1]
图片说明
经过指针i的不断循环判断，发现股票的价格在一直下跌，所以这次的最大收益为现价买入，原价卖出，最大收益为0。当输入为[1,2,3,4,5]时，

初始，i为初始指针指向2，最大收益 $sum = 2 - 1 = 1$ 。

第二次，当i指向3时，最大收益进行累加 $sum += 3 - 2 = 2$ 。
图片说明
第三次，当i指向4时，最大收益进行累加 $sum += 4 - 3 = 3$ 。

第四次，当i指向5时，最大收益进行累加 $sum += 5 - 4 = 4$ ，最后循环终止，最大收益为4。

具体C++代码为：

class Solution {
public:
    /**
     *代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *计算最大收益
     * @param prices int整型vector股票每一天的价格
     * @return int整型
     */
    int maxProfit(vector& prices) {
        // write code here
        int length = prices.size();//价格数组的长度
        int sum = 0;//初始收益为0
        for(int i = 1;i  prices[i - 1])//当第i天的收益大于第i - 1时，计算收益值
                sum += prices[i] - prices[i-1];
        }
        return sum;//返回最大收益
    }
};

因为该算法属于暴力法破解，循环每一天的收益进行判断，所以时间复杂度为 $O(N)$ ，未占用任何额外的内存空间，所以空间复杂度为 $O(1)$ 。

解法二：

思路分析：同样，我们可以采用贪心算法进行计算，不需要将每个值都进行比较和计算，根据上述暴力法分析，我们得出在股票正常上涨的过程中都存在一个起始值和一个起始过程的最大值，也就是一个间断性的增长，通过计算这部分值，然后不断的进行比较，就可以得到股票的最大收益。

实例分析：{1，2，3，4，5}
图片说明
首先我们设置一个index变量用于记录这个增幅的开始阶段，同样用index记录累加的价格范围的下标，最后一减，就能得出最大收益。

根据分析，股票的价格一直在进行上涨，所以直接计算得出最大收益为4。

具体C++代码为：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算最大收益
     * @param prices int整型vector 股票每一天的价格
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        // write code here
        int len = prices.size();
        if(len == 0)//考虑空数组的情况
            return 0;
        if(prices.empty() && len < 2)
            return 2;
        int index = 0;
        int sum = 0;//设置最大收益
        while(index < len){
            while(index < len - 1 && prices[index] >= prices[index + 1])
                index++;//寻找股票开始上涨的点
            int minprices = prices[index];//将刚开始上涨的点称为最低价格
            while(index < len - 1 && prices[index] <= prices[index + 1]){
                index++;//计算上涨的差值进行累加
            }
            sum += prices[index++] - minprices;//计算最终结果值
        }
        return sum;
    }
};

该贪心算法需要寻找所有点的连续阶段最小值和一个连续阶段的最大值，还需要全部判断元素的值，所以其时间复杂度为 $O(N)$ ，不需要构建额外的内存空间，空间复杂度为 $O(1)$ 。