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

题意整理

• 已知股票每一天的价格波动。
• 最多持有一只股，也就是买入时必须卖出之前持有的股。
• 可以无限次买入和卖出股票，求最大收益。

方法一（贪心）

1.解题思路

为了在股票交易中获得最大收益，我们肯定希望在极小值点买入，在邻近的极大值点卖出，由于是邻近的极大值点，所以在买入点和卖出点之间股票肯定是单调递增的（记为最佳交易区间）。故而只需将这个区间内所有的上涨差值累加，即可得到这个区间的最大收益。最后总的最大收益是每个最佳交易区间收益的总和。

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        // 特殊情况判断
        if(prices.length==0||prices==null) return 0;

        int res=0;
        //遍历数组
        for(int i=1;i<prices.length;i++){
            //只要股票价格相对前一天是上涨的，则将差值加到res
            if(prices[i]>prices[i-1]){
                res+=prices[i]-prices[i-1];
            }
        }
        return res;
    }
}

3.复杂度分析

• 时间复杂度：需要遍历一次数组，所以时间复杂度为 。
• 空间复杂度：不需要额外的空间，所以空间复杂度为。

方法二（动态规划）

1.解题思路

在买卖股票的交易过程中，有两个状态。一个是未持有股票的状态（即持有现金的状态，记位cash），另一个是持有股票的状态（记位hold）。最后获得的最大收益一定是未持有股票状态的最大值。我们需要弄清楚每次交易过程中，两种状态之间的关系。

• 当未持有股票时，未持有股票状态的最大值，要么是之前的未持有股票状态最大值，要么是将当前持有的股票卖出，即 。
• 当持有股票时，持有股票状态的最大值，要么是之前的持有股票状态最大值，要么是买入当前股票，即 。

动图展示：

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        // 特殊情况判断
        if(prices.length==0||prices==null) return 0;

        // 初始化两种状态
        int cash=0;
        int hold=-prices[0];
        for(int i=1;i<prices.length;i++){
            //状态转移
            cash=Math.max(cash,hold+prices[i]);
            hold=Math.max(hold,cash-prices[i]);
        }
        return cash;
    }
}

3.复杂度分析

• 时间复杂度：只需要遍历一次数组，所以时间复杂度为。
• 空间复杂度：需要额外常数级别的内存空间，所以空间复杂度为。