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); } }
相关推荐
在深入探讨“java-leetcode题解之Best Time to Buy and Sell Stock III.java”这一文件内容之前,我们需要了解LeetCode平台及其题解的价值。LeetCode是一个专门面向技术面试的在线编程平台,它提供了一系列的编程...
《最佳买卖股票时机II》是LeetCode中的一道经典编程题目,主要涉及动态规划和数组操作的知识点。在这个问题中,我们被赋予一个整数数组`prices`,表示某支股票每天的价格。任务是找到在允许进行多次交易的情况下,...
在JavaScript中,LeetCode题目"Best Time to Buy and Sell Stock III"是一个典型的数据结构和算法问题,通常出现在编程面试和算法训练中。该问题的目标是在给定的股票价格数组中找出最大的利润,但是与简单买卖一次...
python python_leetcode题解之123_Best_Time_to_Buy_and_Sell_Stock_III
本篇Java题解关注的是“Best Time to Buy and Sell Stock IV”(买卖股票的最佳时机 IV),这是该系列问题中的一个变体,涉及动态规划这一算法思想。 首先,需要明确问题的具体要求。在这个变体中,给定一个数组,...
在解决股票交易问题时,程序员们经常会遇到“Best Time to Buy and Sell Stock with Cooldown”这类问题。该问题属于动态规划的经典案例,通常被列为中等难度。在这类问题中,给定一个整数数组表示某只股票的价格,...
- 题目理解:Best Time to Buy and Sell Stock II这道题目的目的是寻找一个最佳的股票买卖时机,使得获得的利润最大化。 - 问题分析:此题是一道典型的动态规划问题,也可以使用贪心算法解决。 - 解题思路:贪心算法...
在探讨python实现leetcode第122题"Best Time to Buy and Sell Stock II"的解决方案前,我们首先需要明确题目要求。第122题属于动态规划和贪心算法范畴,要求编写一个程序,通过分析给定的股票价格数组来找出最大的...
Best Time to Buy and Sell Stock I是LeetCode网站上的一道著名的编程题目,它属于动态规划的范畴。这道题目通常被称为“买卖股票的最佳时机”,主要是考察程序员对动态规划思想的理解和应用。在这个问题中,给定一...
在探讨如何用Python解决LeetCode上的第121题“最佳买卖股票时机”之前,我们有必要对相关概念和解决策略进行充分了解。本题要求找到只进行一次买卖的最大利润,是动态规划算法中的典型问题。 首先,我们要明确题目...
在JavaScript的世界里,LeetCode是一个广受欢迎的在线编程平台,它提供了一系列的算法题目,帮助程序员提升编程技能。其中“121. 买卖股票的最佳时机”是一个经典的动态规划问题,经常作为算法入门的练习题。本题...
在JavaScript(简称JS)编程中,LeetCode题库提供了一系列的编程挑战,旨在帮助开发者提升算法和编程能力。本篇文档将深入分析LeetCode 122号题目,即“买卖股票的最佳时机 II”,并给出一种JS语言的解决方案。此...
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 GitFitCode 配对编码挑战! 买卖股票的最佳时机 让我们弄清楚什么时候买一些股票! 这不应该在现实生活中使用。 现在不管你认为你的算法有多好:)。 我确实鼓励您选择一只您感兴趣的股票,...
leetcode leetcode The optimum C++ solutions for the leetcode 这是我自己写的leetcode的题解,目前已经完成了70%左右,后续部分会很快更新 这里放上来的代码都能保证是最优解(复杂度最优) 当然有些题目因为测试...
股票收益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) ...
- 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...
第一个问题是“Best Time to Buy and Sell Stock”(121题),题目要求找到一次买入和卖出股票的最好时机,使得收益最大化。解决这个问题的一种有效方法是使用线性扫描,遍历数组找到一个局部最小值作为买入点,再...
leetcode LeetCode 解决题目的总数: 136/1753 微信公众号: 工程师Ruojhen 算法-动态规划 题号 名称 English Name 题解 53 最大子序和 Maximum Subarray 70 爬楼梯 Climbing Stairs 121 买卖股票的最佳时机 Best Time...
leetcode 答案 LeetCode-Trip LeetCode刷题代码,大佬勿入。 为一年后的研究生找工作准备 目标是BAT的算法岗哈哈哈哈哈 争取做到每日一更 嗯…… 19.10.22:鸽了这么久,我又回来了……主要在实验室天天没啥事,过于...