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

股票(无限次交易)

http://www.nowcoder.com/practice/9e5e3c2603064829b0a0bbfca10594e9

题目

描述

假定你知道某只股票每一天价格的变动。
你最多可以同时持有一只股票。但你可以无限次的交易（买进和卖出均无手续费）。
请设计一个函数，计算你所能获得的最大收益。

方法一

思路

依据股票状态可以分为交易完后有股票和交易完后无股票；手中有股票的情况分别为：当天买入股票，或者是之前买入的股票没有卖出，此时存在递推公式：
$图片说明$
函数f(i,j),i表示第几天，j表示i天是否持有股票，1表示持有，0表示没有；
而对于交易完后无股票分别为：当天卖出股票，或者当天之前就已经将股票卖出，此时存在递推公式： $图片说明$
故可以采用动态规划，建立dp[n][2]数组，来进行计算最大利润。

具体步骤

1.数组为空，或者元素数为1，返回0即可；
2.创建二维dp数组，辅助运算；
3.依据递推公式进行运算即可。
代码如下：

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算最大收益
     * @param prices int整型一维数组 股票每一天的价格
     * @return int整型
     */
    public int maxProfit (int[] prices) {
        // write code here
        if (prices == null || prices.length < 2)
            return 0;
        int[][] dp = new int[prices.length][2];
        // 初始化dp数组
        dp[0][1] = -prices[0];
        dp[0][0] = 0;

        for (int i = 1; i < prices.length; i++) {
            //递推公式
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        //最后一天肯定是手里没有股票的时候，利润才会最大，
        return dp[prices.length - 1][0];
    }
}

时间复杂度： $O(n)$ ，遍历整个prices数组；
空间复杂度： $O(n)$ ，二维数组dp，元素数为2n，故空间复杂度为 $O(n)$ 。

方法二

思路

由于只有一支股票在交易，且没有买入卖出的手续费，所以只需要在股票下跌前一天卖出，股票上升的前一天买入即可，所以本题就转换成了找出所有股票下跌的时间点以及所有股票上升的时间点。

具体步骤

1.初始化：买入点buy = 0，sale = 1；
2.寻找卖出时间点，比较买入点以及卖出点的差价dis，dis>0,则继续往下遍历；
3.dis<=0,则当天买入当天卖出。
4.循环遍历，直至遍历完整个数组得出最大收益。
参考下图示例：

代码如下：

import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 计算最大收益
* @param prices int整型一维数组 股票每一天的价格
* @return int整型
*/
public int maxProfit (int[] prices) {
   // write code here
   int benefit = 0;
   int buy = 0;
   int sale = 1;
   while(sale < prices.length){
       // 找出股票上涨的阶段
       while(sale < prices.length && prices[sale] > prices[sale-1]){
           sale++;
       }
       // 股票下跌的前一天卖出，而当买入的第二天股票还是下跌时，当天买入当天卖出
       benefit += (prices[sale-1] - prices[buy]) ;
       // 股票下跌时买入
       buy = sale;
       ++sale;
   }
   return benefit;
}
}