Best Time To Buy And Sell Stock 买卖股票最佳时机

elliott_hu 发布于2019-08-15 15:40 / 1828人阅读

摘要：关键字，，算法，，动态规划，上关于主题的题目有四个这四个题目难度依次递增。其中第四个问题是寻求一个通解，在给定和最大买卖次数的情况下，求最大收益。首先大致的解题方向是动态规划，这个应该不难想到。之后就是怎么找到状态，怎么列状态转移方程。

关键字：leetcode，Best Time To Buy And Sell Stock，算法，algorithm，动态规划，dynamic programming

leetcode 上关于Best Time to Buy and Sell Stock主题的题目有四个：

https://leetcode.com/problems...

这四个题目难度依次递增。大致意思就是，给我们一个 List prices ，然后让我们找到怎么买卖才能获得最大收益。其中第四个问题是寻求一个通解，在给定 prices和最大买卖次数k的情况下，求最大收益。

首先大致的解题方向是动态规划，这个应该不难想到。之后就是怎么找到状态，怎么列状态转移方程。考虑某一天的情况，可以有如下三种状态：

当天买入

当天卖出

当天什么也没做

因为这个题目我们要找到最大收益，所以，如果最后一天的状态是买入的话，那么其收益一定不是最大的，因为最后一天买入的话，就没有机会卖出了。那么，上面的三个状态可以减少到两个：

当天卖出。

卖出，但是不在当天（即在前面的某一天）。

所以，我们用 soldAtToday[k] 来表示当天卖出且卖出的时候交易了 k 手的时候的最大收益，soldNotAtToday[k] 代表在之前某天卖出，且当前交易手数为 k 的时候的最大收益。那么，状态转移方程就可以用如下伪代码描述：

soldAtToday[k] =  max(soldAtYesterday[k] + price, soldNotAtYesterday[k - 1] + price);
soldNotAtToday[k] = max(soldAtYesterday[k], soldNotAtYesterday[k]);

其中，k 是交易次数。需要注意的是soldAtToday[k] = max(soldAtYesterday[k] + price, soldNotAtYesterday[k - 1] + price);中第一个备选项是soldAtYesterday[k]，而不是soldAtYesterday[k - 1]，其含义就是，把本应该昨天卖的延长一天到今天卖，所以交易次数还是 k 。

具体实现的时候，我们发现 soldAtToday 和 soldNotAtToday 都是只依赖于 soldAtYesterday 和 soldNotAtYesterday，所以我们可以利用两个长度为 k + 1 的数组来完成 today 和 yesterday 数据的存储。

package BestTimeToBuyAndSellStock.VersionIV;

@SuppressWarnings("Duplicates")
class Solution {

    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;
    }

    public int maxProfit(int k, int[] prices) {
        if (prices == null || prices.length <= 1 || k <= 0) {
            return 0;
        }

        int len = prices.length;

        if (k >= len / 2) return quickSolve(prices);


        int today = 1;
        int yesterday = 0;
        int[][] soldAt = new int[2][k + 1];
        int[][] soldNotAt = new int[2][k + 1];

        soldAt[today][0] = 0;
        soldAt[yesterday][0] = 0;
        soldNotAt[today][0] = 0;
        soldNotAt[yesterday][0] = 0;

        for (int i = 0; i < k + 1; i++) {
            soldAt[yesterday][i] = 0;
            soldNotAt[yesterday][i] = 0;
        }

        for (int i = 1; i < prices.length; i++) {
            int price = prices[i] - prices[i - 1];
            for (int j = 1; j < k + 1; j++) {
                soldAt[today][j] = Math.max(
                        soldAt[yesterday][j] + price,
                        soldNotAt[yesterday][j - 1] + price
                );
                soldNotAt[today][j] = Math.max(
                        soldAt[yesterday][j],
                        soldNotAt[yesterday][j]
                );
            }
            int tmp = yesterday;
            yesterday = today;
            today = tmp;
        }

        return Math.max(soldAt[yesterday][k], soldNotAt[yesterday][k]);
    }
}

观察代码发现，开头多了一个 quickSolve 。这是因为，如果直接把上面我们描述的算法实现出来，提交上去，会出现 TimeLimted 的问题。仔细分析了一下超时的用例，发现他们的特征是 k 很大。其实，当 k 大于 prices.length / 2 的时候，就相当于没有 k 的限制，即随便买卖了，因为不考虑当天买当天卖的情况，或者把当天买卖的收益虚拟的记为 0 。那么我们的算法就退化成最简单的情况，于是使用一个 quickSolve 来解决即可。
这个题目也对我们日常工作提供了启示：出现问题了，找到瓶颈，分析特征，然后突破。

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69203.html

[Leetcode] Best Time to Buy and Sell Stock 买卖股票的最佳

摘要：双指针法复杂度时间空间思路根据买卖股票的特性，我们必须先低价买，再高价卖，这个找最大收益的过程实际上是找到目前为之的最低价。我们可以利用这个之前计算的结果降低时间复杂度不过代价是额外空间，所以需要把到的最大收益存在数组中。 Best Time to Buy and Sell Stock I Say you have an array for which the ith element...

nanchen2251 2019-08-14 16:11 评论0 收藏0
[LeetCode]Best Time to Buy and Sell Stock with Coo

摘要：分析因为当前日期买卖股票会受到之前日期买卖股票行为的影响，首先考虑到用解决。所以我们可以用两个数组分别记录当前持股跟未持股的状态。 Best Time to Buy and Sell Stock with Cooldown Say you have an array for which the ith element is the price of a given stock on ...

xcc3641 2019-08-14 15:08 评论0 收藏0
LeetCode 309. Best Time to Buy and Sell Stock with

摘要：示例输入输出解释对应的交易状态为买入卖出冷冻期买入卖出思路这道题使用动态规划。状态表示当天休息能够获得的最大价值，表示当天持有股票能够获得的最大价值，表示当天持有股票能够获得的最大价值。 Description Say you have an array for which the ith element is the price of a given stock on day i. ...

刘明 2019-07-31 10:04 评论0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月汇总（55 题攻略）

摘要：微信公众号记录截图记录截图目前关于这块算法与数据结构的安排前。已攻略返回目录目前已攻略篇文章。会根据题解以及留言内容，进行补充，并添加上提供题解的小伙伴的昵称和地址。本许可协议授权之外的使用权限可以从处获得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目录不...

warmcheng 2019-08-26 10:09 评论0 收藏0
Leetcode188. Best Time to Buy and Sell Stock IV

摘要：题目要求有一个整数数组，每一位上的值代表那一天的股票价格。现在假设最多能够进行次交易，问最大的收入是多少思路和代码这里采用了动态编程的思想。题目要求 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 t...

pingink 2019-08-15 14:20 评论0 收藏0