leetcode188.Best Time to Buy and Sell Stock IV

发表于 更新于 分类于 ，

题目要求

1
2
3
4
5
6
Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

有一个整数数组，每一位上的值代表那一天的股票价格。现在假设最多能够进行k次交易，问最大的收入是多少？

思路和代码

这里采用了动态编程的思想。假设我们希望得到第j天最多进行i次交易的最大利润，我们首先想到的是，可以通过比较第j-1天最多进行i次交易的利润，以及第j-1天进行i-1次交易然后最后一次交易为卖出当天的股票所带来的利润。

但是这里存在一个问题，也就是说，如果第j-1天进行的第i-1次交易刚好为卖出第j-1天的股票，而我们不能在这个数据上直接加上在第j天出售股票所获得的利润，因为我们在j-1天根本就没有购入股票！所以我们需要在j-1天进行i-1次交易获得最大利润的基础上减去第j天的股票代表我们买入了第j天的股票，从而用于下一轮的计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int maxProfit(int k, int[] prices) {
    int len = prices.length;
    if (k >= len / 2) return quickSolve(prices);
    
    int[][] t = new int[k + 1][len];
    for (int i = 1; i <= k; i++) {
        int tmpMax =  -prices[0];
        for (int j = 1; j < len; j++) {
            t[i][j] = Math.max(t[i][j - 1], prices[j] + tmpMax);
            tmpMax =  Math.max(tmpMax, t[i - 1][j - 1] - prices[j]);
        }
    }
    return t[k][len - 1];
}


private int quickSolve(int[] prices) {
    int len = prices.length, profit = 0;
    for (int i = 1; i < len; i++)
        // as long as there is a price gap, we gain a profit.
        if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
    return profit;
}