交易次数分别为一次和无限次的股票交易问题

1、交易次数限制为一次的情况：

题目：

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。

注意：你不能在买入股票前卖出股票

分析：

由于交易的次数被限制为一次，所以我们要找的就是在这几天当中股票价格的最低值以及这之后的股票价格的最高值，相减就是最大利润。

方法一：

贪心思想，找出当前这个日子之前的股票最低价格买入，然后判断以当前股票价格卖出是否是截止到目前为止的最大值。贪心思想在做出选择时，就是直接做出当前问题中

看起来的最优解。

实现代码如下：

    public int maxProfit(int[] prices) {
        if (prices==null || prices.length < 2)
            return 0;

        int min_price = prices[0];
        int max= 0;

        for (int price : prices) {
            if (min_price > price)
                min_price = price;
            else {
                max = Math.max(price-min_price,max);
            }
        }
        return max;
    }

方法二：

动态规划，

　　1.定义一个状态转移数组dp，表示当前的获得的最大利润，dp[i][0]表示在第i天，没有持有股票的最大利润；dp[i][1]表示在第i天，持有股票时的最大利润。

　　2.状态转移方程：

　　　　dp[i][0] = max{dp[i-1][0],dp[i-1][1]+price[i-1]} 表示当前没有持有可能是前一天也没有持有股票，也可能是前一天持有股票，今天出售了

　　　　dp[i][1] = max{dp[i-1][1],-price[ii-1]}　　表示当前持有股票的原因可能是前一天也持有了股票而今天没有卖，也可能是前一天没有持有股票，今天购买了

　　3.dp[1][0] = 0,dp[1][1] = -price[0]

通过观察状态方程可以发现，第i天的利润只和第i-1天有关，因此可以将这个维度去掉，将状态数组替换为状态转移变量，从而减少空间复杂度。

    public int maxProfit2(int[] prices) {
        if (prices==null || prices.length < 2)
            return 0;
        int dp_i_0 = 0;
        int dp_i_1 = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            dp_i_0 = Math.max(dp_i_0,dp_i_1+prices[i]);
            dp_i_1 = Math.max(dp_i_1,-prices[i]);
        }
        return dp_i_0;
    }

2、交易次数限制为一次的情况：

题目：

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

分析：

方法一：

贪心思想，交易次数是无限制的，从最理想的情况来看是从第一天开始到最后一天股票价格都是一直增长的，那么此时所有的price[i] > price[i-1]都成立，所以最大利润就是

price[n-1] - price[0]；但是在实际的情况中，股票价格肯定是有波动的，也就是存在着price[i] < price[i]的情况，那么我们依据贪心思想，考虑在当前的第i天，如果price[i] > price[i-1]成立，那么就是第i-1天买入，第i天卖出，股价之差就算入总利润，最大的利润就是所有的price[i] > price[i-1]情况相加。

    public int maxProfit(int[] prices) {
        if (prices==null || prices.length<2)
            return 0;
        int profit = 0;

        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i-1])
                profit += (prices[i]-prices[i-1]);
        }
        return profit;
    }

方法二：

动态规划，由于交易次数是无限的，所以我们可以不明确表示交易次数这个状态，定义一个状态转移数组表示当前的获得的最大利润，dp[i][0]表示在第i天，没有持有股票的最大利润；dp[i][1]表示在第i天，持有股票时的最大利润。

　　确定状态转移方程：

　　　　dp[i][0] = max{dp[i-1][0],dp[i-1][1]+price[i-1]} 表示当前没有持有可能是前一天也没有持有股票，也可能是前一天持有股票，今天出售了

　　　　dp[i][1] = max{dp[i-1][1],dp[i-1][0]-price[i-1]}　表示当前持有股票的原因可能是前一天也持有了股票而今天没有卖，也可能是前一天没有持有股票，今天购买了

此处与交易次数限制为1次的时候的最大区别是我们在考虑dp[i][1]的值的时候，选择范围是当前一天也持有了股票而今天没有卖，或者是前一天没有持有股票，今天购买了。而今天购买了，那么总体的利润就变成了前一天没有持有的股票的时候拥有的最大利润减去今天购买的股票价格，也就是说因为交易次数是无限的，所以前一天所拥有的利润可能不为0，所以也就需要明确考虑，而交易次数限制为1次的时候，假如第i天要购买股票，那么第i天之前是没有发生交易的，所以也就没有利润，利润值为0，这是最大的区别。

    public int maxProfit2(int[] prices) {
        int n = prices.length;
        if (prices==null || n<2)
            return 0;

        int[][] dp = new int[n + 1][2];
        dp[1][0] = 0;
        dp[1][1] = -prices[0];

        for (int i = 2; i <= n; i++) {
            dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]+prices[i-1]);
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i-1]);
        }
        return dp[n][0];
    }

交易次数分别为一次和无限次的股票交易问题

相关推荐