买卖股票最佳时机

题目主要信息

假设你有一个数组prices，长度为n，其中prices[i]是某只股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益

1. 你最多可以对该股票有kk笔交易操作，一笔交易代表着一次买入与一次卖出，但是再次购买前必须卖出之前的股票
2. 如果不能获取收益，请返回0
3. 假设买入卖出均无手续费

方法一：动态规划

具体方法

对于买卖股票无外乎就两种状态，买和卖，因此我们可以设置存储两种状态的数组，一组存买入$buybuy$，一组存卖出$sellsell$。

用$buy[i][j]buy[i]\; [j]$表示对数组 $prices[\mathrm{0...}i]prices[0...i]$中的价格，进行了 j笔交易，并且当前手上还有一支股票下的最大利润。用 $sell[i][j]sell[i]\; [j]$表示恰好进行j笔交易，并且手上没有股票下的最大利润。

可以推到两者的状态转移方程，对于$buy[i][j]buy[i]\; [j]$，需要考虑当前手上的股票是当天买的还是前一天遗留的。因此

$buy[i][j]=max\mathrm{（}buy[i-1][j],sell[i-1][j]-price[i]\mathrm{）}buy[i]\; [j]\; =\; max（buy[i-1]\; [j],sell[i-1]\; [j]\; -\; price[i]\; ）$

对于$sell[i][j]=max\mathrm{（}sell[i-1][j],buy[i-1][j-1]+price[i]\mathrm{）}sell[i]\; [j]\; =\; max（sell[i-1]\; [j],buy[i-1]\; [j-1]+price[i]）$

$nn$天结束后，手上不持有股票对应的最大利润一定是严格由于手上持有股票对应的最大利润的，然而完成的交易数并不是越多越好（例如数组 prices 单调递减，我们不进行任何交易才是最优的），因此最终的答案即为 $sell[n-1][\mathrm{0..}k]sell[n-1]\; [0..k]$中的最大值。

Java代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prices int整型一维数组 
     * @param k int整型 
     * @return int整型
     */
    public int maxProfit (int[] prices, int k) {
        // write code here
        //先判断数组长度是否为0
         if (prices.length == 0) {
            return 0;
        }

        //得到最小的k 因为买卖两个算一个组合 
        int n = prices.length;
        k = Math.min(k, n / 2);
        int[][] buy = new int[n][k + 1];
        int[][] sell = new int[n][k + 1];

        //初始值
        buy[0][0] = -prices[0];
        sell[0][0] = 0;
        //保证相加的时候不溢出
        for (int i = 1; i <= k; ++i) {
            buy[0][i] = sell[0][i] = Integer.MIN_VALUE/2;
        }
        //两层for循环 
        for (int i = 1; i < n; ++i) {
            buy[i][0] = Math.max(buy[i - 1][0], sell[i - 1][0] - prices[i]);
            for (int j = 1; j <= k; ++j) {
                buy[i][j] = Math.max(buy[i - 1][j], sell[i - 1][j] - prices[i]);
                sell[i][j] = Math.max(sell[i - 1][j], buy[i - 1][j - 1] + prices[i]);   
            }
        }
        return Arrays.stream(sell[n - 1]).max().getAsInt();
    }
}

复杂度分析

• 时间复杂度分析：$O(nk)O(n\; k)$,其中n是数组prices的大小，由于需要两层循环，所以时间复杂度是两者相乘。
• 空间复杂度分析：$O(nk)O(n\; k)$,由于设置的两维的数组。

方法二：空间压缩

具体方法

根据方法一可以知道买$buy[i][j]buy[i]\; [j]$和$sell[i][j]sell[i]\; [j]$ 都跟前一天的状态有关，所以可以将前一天的状态存下来，这样就可以避免使用两维数组了。状态转移方程$buy[j]buy[j]$和$sell[j]sell[j]$ 分别为

$buy[j]=maxbuy[j],sell[j]-price[i]buy[j]\; =\; max\{buy[j],sell[j]-price[i]\}$

$Sel[j]=maxsell[j],buy[j-1]+price[i]Sel[j]\; =\; max\{sell[j],buy[j-1]+price[i]\}$

Java代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param prices int整型一维数组 
     * @param k int整型 
     * @return int整型
     */
    public int maxProfit (int[] prices, int k) {
        // write code here
        //先判断数组长度是否为0
        if (prices.length == 0) {
            return 0;
        }
        // prices的长度
        int n = prices.length;
        k = Math.min(k, n / 2);
        int[] buy = new int[k + 1];
        int[] sell = new int[k + 1];
        //初始化初值
        buy[0] = -prices[0];
        sell[0] = 0;
        //初始化
        for (int i = 1; i <= k; ++i) {
            buy[i] = sell[i] = Integer.MIN_VALUE / 2;
        }

        for (int i = 1; i < n; ++i) {
            buy[0] = Math.max(buy[0], sell[0] - prices[i]);
            for (int j = 1; j <= k; ++j) {
                buy[j] = Math.max(buy[j], sell[j] - prices[i]);
                sell[j] = Math.max(sell[j], buy[j - 1] + prices[i]);   
            }
        }
        //返回最后一个 
        return Arrays.stream(sell).max().getAsInt();
    }
}

复杂度分析

• 时间复杂度：$O(nmin(n,k))O(n\; min(n,k))$其中n为数组prices的大小。
• 空间复杂度：$O(k)O(k)$，使用一维的数组。