Leetcode188. Best Time to Buy and Sell Stock IV

pingink 发布于2019-08-15 14:20 / 2823人阅读

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

题目要求

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天的股票，从而用于下一轮的计算。

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

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

私有云服务器托管 redis Time to live Buy Sell Stock

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

转载请注明本文地址：https://www.ucloud.cn/yun/68551.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
Best Time To Buy And Sell Stock 买卖股票最佳时机

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

elliott_hu 2019-08-15 15:40 评论0 收藏0
leetcode 121 Best Time to Buy and Sell Stock

摘要：求可能的最大利润题目给了两个例子最大利润就是进价为，卖价为的时候，利润为在这个案例中，进价一直高于售价，所以无法成交，返回。主要注意一下，先买入才能卖出卖价一定要比买入价格高才能成交就可以了。题目详情 Say you have an array for which the ith element is the price of a given stock on day i.If yo...

QLQ 2019-08-15 13:39 评论0 收藏0