`

Leetcode - Best Time to Buy and Sell Stock III

 
阅读更多

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 two transactions.

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

 

[balabala] 自己的想法是先找出收益最大的一笔收益,然后从剩余区间中寻找次大的收益,但是在一些case上会失败,比如 [6,1,3,2,4,7]。为什么这种贪婪做法得不到全局最优解呢?如yb君指点,因为第一次交易确定会影响第二次交易的可选范围,子问题之间相互影响,所以不可用最优子问题叠加获取最优解。
正确的思路:至多能做两笔交易,而且交易之间没有重叠,想到可以用divide and conque. 如yb君说,需要综合使用多种算法的题目就会显得比较难。这题就是分治 + 动归 综合题。

 

public class Solution {
    // 以每一天为分界点,分别求出左边和右边能获得的最大收益,然后求出最大值
    // 分治 + 动归
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2)
            return 0;
        
        int[] left = new int[prices.length];
        int low = prices[0];
        int maxleft = 0;
        for (int i = 0; i < prices.length; i++) {
            left[i] = Math.max(maxleft, prices[i] - low);
            low = Math.min(low, prices[i]);
        }
        
        int[] right = new int[prices.length];
        int high = prices[prices.length - 1];
        int maxright = 0;
        for (int i = prices.length - 1; i >=0 ;i--) {
            right[i] = Math.max(maxright, high - prices[i]);
            high = Math.max(high, prices[i]); 
        }
        
        int maxprofit = 0;
        for (int i = 0; i < prices.length; i++) {
            maxprofit = Math.max(maxprofit, left[i] + right[i]);
        }
    }
    
    ////////////////////////////////下面为不正确思路的实现//////////////////////////////
    //fail @ [6,1,3,2,4,7]
    class ProfitInfo {
        int buyDay;
        int sellDay;
        int profit;
        public ProfitInfo(int buyDay, int sellDay, int profit) {
            this.buyDay = buyDay;
            this.sellDay = sellDay;
            this.profit = profit;
        }
    }
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2)
            return 0;
        ProfitInfo profit1 = maxProfit(prices, 0, prices.length - 1);
        ProfitInfo profit2 = maxProfit(prices, 0, profit1.buyDay - 1);
        ProfitInfo profit3 = maxProfit(prices, profit1.sellDay + 1, prices.length - 1);
        return profit1.profit + Math.max(profit2.profit, profit3.profit);
    }
    
    private ProfitInfo maxProfit(int[] prices, int start, int end) {
        if (start >= end) // length of range <= 1
            return new ProfitInfo(start, end, 0);
        int min = start;
        int buy = start;
        int profit = 0;
        int sell = start;
        for (int i = start + 1; i <= end; i++) {
            if (prices[i] < prices[min]) {
                min = i;
            } else if (prices[i] > prices[min]){
                int currProfit = prices[i] - prices[min];
                if (currProfit >= profit) {
                    profit = currProfit;
                    buy = min;
                    sell = i;
                }
            }
        }
        return new ProfitInfo(buy, sell, profit);
    }
    
    // fail @ [2, 4, 1] buy不能同时承担最小价格日以及当前最大profit的购买日,两者不一定是同一个值
    private ProfitInfo maxProfit(int[] prices, int start, int end) {
        if (start >= end) // length of range <= 1
            return new ProfitInfo(start, end, 0);
        int buy = start;
        int profit = 0;
        int sell = start;
        for (int i = start + 1; i <= end; i++) {
            if (prices[i] < prices[buy]) {
                buy = i;
            } else if (prices[i] > prices[buy]){
                int currProfit = prices[i] - prices[buy];
                if (currProfit >= profit) {
                    profit = currProfit;
                    sell = i;
                }
            }
        }
        return new ProfitInfo(buy, sell, profit);
    }
}

 

分享到:
评论
4 楼 qb_2008 2015-04-24  
我想到的是一维动态规划的扩展,时间复杂度应该是O(n*k),类似装配链的扩展,从左到右在每个点对所有可能状态找最优值。
3 楼 likesky3 2015-04-23  
这道题确实还有个升级版,求解交易k次的最大利润,想了好久也没想出O(N)的做法……笨方法妥妥地超时
2 楼 likesky3 2015-04-23  
你的实现更简洁些,我遵照你之前教导我的,先写熟练了再考虑简洁代码~ 分治的子问题是完全独立的,但动归中子问题通常伴随有重复,正因为动归存储了子问题结果避免了重复子问题计算从而收获高效。
1 楼 qb_2008 2015-04-23  
局部最优不代表全局最优,找到最赚钱的两笔交易,不代表需要找到最赚钱的那笔交易。因为交易不能重叠。
就像例子[6,1,3,2,4,7]中,最赚钱的一笔交易为[1,7],但用它全局只能赚6,实际上最赚钱的两笔交易为
[1,3]和[2,7],全局可以赚7.因为找的第一笔交易会影响第二笔交易的可选范围,子问题间相互影响,所以
不可用最优子问题叠加来得到最优全局解。
最简单的算法O(n^3),选择两个起点,然后找对应最好的重点。
但实际上因为恰好是两个交易,可以先做出两个数组,用O(n)求解。
MinPrev[i] 代表<=i的最小stock值,MaxPost[i]代表>=i的最大stock值。
int max_earn = 0;
int max_first_earn = 0;
for (i = 0; i < n; ++i) {
  // 以i为第二笔交易的起点,earn为在这种情况下最多赚多少.
  int earn = max_first_earn + MaxPost[i] - s[i];
  max_earn = Max(max_earn, earn);
  max_first_earn = Max(max_first_earn, s[i] - MinPrev[i]);
}
当然,你最上面的解法更清晰,我只是突然想到这一种。我觉得这个不太像分治和动归,
我理解的分治是把问题分解,子问题之间没有任何影响;而动归是把问题规模减小,由子问题组合
出问题解,子问题之间也不会相互影响。
我觉得这道题更像是从求最赚一笔交易的问题延伸而来的。求最赚两笔,就把数组分两截,分别求最赚一笔交易;
求最赚三笔,就把数组分三截,分别求最赚一笔交易。如果不限交易数,似乎是个不错的问题。我似乎发现了
都是O(n)的解法。

相关推荐

    java-leetcode题解之Best Time to Buy and Sell Stock III.java

    在深入探讨“java-leetcode题解之Best Time to Buy and Sell Stock III.java”这一文件内容之前,我们需要了解LeetCode平台及其题解的价值。LeetCode是一个专门面向技术面试的在线编程平台,它提供了一系列的编程...

    leetcode题目:Best Time to Buy and Sell Stock II

    《最佳买卖股票时机II》是LeetCode中的一道经典编程题目,主要涉及动态规划和数组操作的知识点。在这个问题中,我们被赋予一个整数数组`prices`,表示某支股票每天的价格。任务是找到在允许进行多次交易的情况下,...

    js-leetcode题解之123-best-time-to-buy-and-sell-stock-iii.js

    在JavaScript中,LeetCode题目"Best Time to Buy and Sell Stock III"是一个典型的数据结构和算法问题,通常出现在编程面试和算法训练中。该问题的目标是在给定的股票价格数组中找出最大的利润,但是与简单买卖一次...

    python-leetcode题解之123-Best-Time-to-Buy-and-Sell-Stock-III

    python python_leetcode题解之123_Best_Time_to_Buy_and_Sell_Stock_III

    java-leetcode题解之Best Time to Buy and Sell Stock IV.java

    本篇Java题解关注的是“Best Time to Buy and Sell Stock IV”(买卖股票的最佳时机 IV),这是该系列问题中的一个变体,涉及动态规划这一算法思想。 首先,需要明确问题的具体要求。在这个变体中,给定一个数组,...

    java-leetcode题解之Best Time to Buy and Sell Stock with Cooldown

    在解决股票交易问题时,程序员们经常会遇到“Best Time to Buy and Sell Stock with Cooldown”这类问题。该问题属于动态规划的经典案例,通常被列为中等难度。在这类问题中,给定一个整数数组表示某只股票的价格,...

    java-leetcode题解之Best Time to Buy and Sell Stock II.java

    - 题目理解:Best Time to Buy and Sell Stock II这道题目的目的是寻找一个最佳的股票买卖时机,使得获得的利润最大化。 - 问题分析:此题是一道典型的动态规划问题,也可以使用贪心算法解决。 - 解题思路:贪心算法...

    python-leetcode题解之122-Best-Time-to-Buy-and-Sell-Stock-II

    在探讨python实现leetcode第122题"Best Time to Buy and Sell Stock II"的解决方案前,我们首先需要明确题目要求。第122题属于动态规划和贪心算法范畴,要求编写一个程序,通过分析给定的股票价格数组来找出最大的...

    java-leetcode题解之Best Time to Buy and Sell Stock I.java

    Best Time to Buy and Sell Stock I是LeetCode网站上的一道著名的编程题目,它属于动态规划的范畴。这道题目通常被称为“买卖股票的最佳时机”,主要是考察程序员对动态规划思想的理解和应用。在这个问题中,给定一...

    python-leetcode题解121-Best-Time-to-Buy-and-Sell-Stock

    在探讨如何用Python解决LeetCode上的第121题“最佳买卖股票时机”之前,我们有必要对相关概念和解决策略进行充分了解。本题要求找到只进行一次买卖的最大利润,是动态规划算法中的典型问题。 首先,我们要明确题目...

    js-leetcode题解之121-best-time-to-buy-and-sell-stock.js

    在JavaScript的世界里,LeetCode是一个广受欢迎的在线编程平台,它提供了一系列的算法题目,帮助程序员提升编程技能。其中“121. 买卖股票的最佳时机”是一个经典的动态规划问题,经常作为算法入门的练习题。本题...

    js-leetcode题解之122-best-time-to-buy-and-sell-stock-ii.js

    在JavaScript(简称JS)编程中,LeetCode题库提供了一系列的编程挑战,旨在帮助开发者提升算法和编程能力。本篇文档将深入分析LeetCode 122号题目,即“买卖股票的最佳时机 II”,并给出一种JS语言的解决方案。此...

    javalruleetcode-leetcode-java:力码笔记

    java lru leetcode leetcode-java leetcode刷题笔记 ...III 141.Linked List Cycle 142.Linked List Cycle II 188.Best Time to Buy and Sell Stock IV 217.Contains Duplicate 263.Ugly Number 264.Ugly Number II

    股票买卖最佳时机leetcode-best-time-to-buy-and-sell-stock:让我们弄清楚什么时候买一些股票!这不应该在现

    股票买卖最佳时机leetcode GitFitCode 配对编码挑战! 买卖股票的最佳时机 让我们弄清楚什么时候买一些股票! 这不应该在现实生活中使用。 现在不管你认为你的算法有多好:)。 我确实鼓励您选择一只您感兴趣的股票,...

    leetcode-leetcode:leetcode的最佳C++解决方案

    leetcode leetcode The optimum C++ solutions for the leetcode 这是我自己写的leetcode的题解,目前已经完成了70%左右,后续部分会很快更新 这里放上来的代码都能保证是最优解(复杂度最优) 当然有些题目因为测试...

    股票收益leetcode-leetcode:leetcode摘要

    股票收益leetcode LeetCode 股票问题 Best Time to Buy and Sell Stock (Easy) 一次交易,找最大收益 for i in prices: low = min(low, i) profit = max(profit, i-low) Best Time to Buy and Sell Stock II (Easy) ...

    3、动态规划必练题(含解法).pdf

    - Best Time to Buy and Sell Stock III:存在多日限制交易,最多两次交易。 - Best Time to Buy and Sell Stock IV:与前三者不同,可能需要多次买入和卖出。 - Best Time to Buy and Sell Stock with Cooldown...

    leetcode-常见考题4.pdf

    第一个问题是“Best Time to Buy and Sell Stock”(121题),题目要求找到一次买入和卖出股票的最好时机,使得收益最大化。解决这个问题的一种有效方法是使用线性扫描,遍历数组找到一个局部最小值作为买入点,再...

    lrucacheleetcode-LeetCode:CppSourceCode的LeetCode解决方案

    leetcode LeetCode 解决题目的总数: 136/1753 微信公众号: 工程师Ruojhen 算法-动态规划 题号 名称 English Name 题解 53 最大子序和 Maximum Subarray 70 爬楼梯 Climbing Stairs 121 买卖股票的最佳时机 Best Time...

    leetcode答案-LeetCode-Trip:LeetCode刷题代码,大佬勿入

    leetcode 答案 LeetCode-Trip LeetCode刷题代码,大佬勿入。 为一年后的研究生找工作准备 目标是BAT的算法岗哈哈哈哈哈 争取做到每日一更 嗯…… 19.10.22:鸽了这么久,我又回来了……主要在实验室天天没啥事,过于...

Global site tag (gtag.js) - Google Analytics