- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
假设我们有一个由 n 个整数组成的数组,表示一天的股票价格。我们想要找到一对 (buyDay, sellDay),其中buyDay ≤ sellDay,这样如果我们在buyDay 买入股票并在sellDay 卖出,我们的利润将最大化。
显然,通过尝试所有可能的(buyDay、sellDay)对并从所有对中取出最好的对,该算法有一个 O(n2) 解决方案。但是,是否有更好的算法,也许是在 O(n) 时间内运行的算法?
最佳答案
我喜欢这个问题。这是一个经典的面试问题,根据你的想法,你最终会得到越来越好的解决方案。当然可以在比 O(n2) 时间更好的时间内做到这一点,我在这里列出了三种不同的方式来思考这个问题。希望这能回答你的问题!
一是分治法。让我们看看我们是否可以通过将输入分成两半,解决每个子数组中的问题,然后将两者组合在一起来解决这个问题。事实证明,我们实际上可以做到这一点,而且可以有效地做到这一点!直觉如下。如果我们只有一天,最好的选择是在当天买入,然后在同一天卖出,没有利润。否则,将数组分成两半。如果我们考虑最佳答案可能是什么,它必须位于以下三个位置之一:
T(1) <= O(1)
T(n) <= 2T(n / 2) + O(n)
T(1) <= O(1)
T(n) <= 2T(n / 2) + O(1)
5 10 4 6 7
min 5 5 4 4 4
best (5,5) (5,10) (5,10) (5,10) (5,10)
5 10 4 6 12
min 5 5 4 4 4
best (5,5) (5,10) (5,10) (5,10) (4,12)
1 2 3 4 5
min 1 1 1 1 1
best (1,1) (1,2) (1,3) (1,4) (1,5)
# Four different algorithms for solving the maximum single-sell profit problem,
# each of which have different time and space complexity. This is one of my
# all-time favorite algorithms questions, since there are so many different
# answers that you can arrive at by thinking about the problem in slightly
# different ways.
#
# The maximum single-sell profit problem is defined as follows. You are given
# an array of stock prices representing the value of some stock over time.
# Assuming that you are allowed to buy the stock exactly once and sell the
# stock exactly once, what is the maximum profit you can make? For example,
# given the prices
#
# 2, 7, 1, 8, 2, 8, 4, 5, 9, 0, 4, 5
#
# The maximum profit you can make is 8, by buying when the stock price is 1 and
# selling when the stock price is 9. Note that while the greatest difference
# in the array is 9 (by subtracting 9 - 0), we cannot actually make a profit of
# 9 here because the stock price of 0 comes after the stock price of 9 (though
# if we wanted to lose a lot of money, buying high and selling low would be a
# great idea!)
#
# In the event that there's no profit to be made at all, we can always buy and
# sell on the same date. For example, given these prices (which might
# represent a buggy-whip manufacturer:)
#
# 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
#
# The best profit we can make is 0 by buying and selling on the same day.
#
# Let's begin by writing the simplest and easiest algorithm we know of that
# can solve this problem - brute force. We will just consider all O(n^2) pairs
# of values, and then pick the one with the highest net profit. There are
# exactly n + (n - 1) + (n - 2) + ... + 1 = n(n + 1)/2 different pairs to pick
# from, so this algorithm will grow quadratically in the worst-case. However,
# it uses only O(1) memory, which is a somewhat attractive feature. Plus, if
# our first intuition for the problem gives a quadratic solution, we can be
# satisfied that if we don't come up with anything else, we can always have a
# polynomial-time solution.
def BruteForceSingleSellProfit(arr):
# Store the best possible profit we can make; initially this is 0.
bestProfit = 0;
# Iterate across all pairs and find the best out of all of them. As a
# minor optimization, we don't consider any pair consisting of a single
# element twice, since we already know that we get profit 0 from this.
for i in range(0, len(arr)):
for j in range (i + 1, len(arr)):
bestProfit = max(bestProfit, arr[j] - arr[i])
return bestProfit
# This solution is extremely inelegant, and it seems like there just *has* to
# be a better solution. In fact, there are many better solutions, and we'll
# see three of them.
#
# The first insight comes if we try to solve this problem by using a divide-
# and-conquer strategy. Let's consider what happens if we split the array into
# two (roughly equal) halves. If we do so, then there are three possible
# options about where the best buy and sell times are:
#
# 1. We should buy and sell purely in the left half of the array.
# 2. We should buy and sell purely in the right half of the array.
# 3. We should buy in the left half of the array and sell in the right half of
# the array.
#
# (Note that we don't need to consider selling in the left half of the array
# and buying in the right half of the array, since the buy time must always
# come before the sell time)
#
# If we want to solve this problem recursively, then we can get values for (1)
# and (2) by recursively invoking the algorithm on the left and right
# subarrays. But what about (3)? Well, if we want to maximize our profit, we
# should be buying at the lowest possible cost in the left half of the array
# and selling at the highest possible cost in the right half of the array.
# This gives a very elegant algorithm for solving this problem:
#
# If the array has size 0 or size 1, the maximum profit is 0.
# Otherwise:
# Split the array in half.
# Compute the maximum single-sell profit in the left array, call it L.
# Compute the maximum single-sell profit in the right array, call it R.
# Find the minimum of the first half of the array, call it Min
# Find the maximum of the second half of the array, call it Max
# Return the maximum of L, R, and Max - Min.
#
# Let's consider the time and space complexity of this algorithm. Our base
# case takes O(1) time, and in our recursive step we make two recursive calls,
# one on each half of the array, and then does O(n) work to scan the array
# elements to find the minimum and maximum values. This gives the recurrence
#
# T(1) = O(1)
# T(n / 2) = 2T(n / 2) + O(n)
#
# Using the Master Theorem, this recurrence solves to O(n log n), which is
# asymptotically faster than our original approach! However, we do pay a
# (slight) cost in memory usage. Because we need to maintain space for all of
# the stack frames we use. Since on each recursive call we cut the array size
# in half, the maximum number of recursive calls we can make is O(log n), so
# this algorithm uses O(n log n) time and O(log n) memory.
def DivideAndConquerSingleSellProfit(arr):
# Base case: If the array has zero or one elements in it, the maximum
# profit is 0.
if len(arr) <= 1:
return 0;
# Cut the array into two roughly equal pieces.
left = arr[ : len(arr) / 2]
right = arr[len(arr) / 2 : ]
# Find the values for buying and selling purely in the left or purely in
# the right.
leftBest = DivideAndConquerSingleSellProfit(left)
rightBest = DivideAndConquerSingleSellProfit(right)
# Compute the best profit for buying in the left and selling in the right.
crossBest = max(right) - min(left)
# Return the best of the three
return max(leftBest, rightBest, crossBest)
# While the above algorithm for computing the maximum single-sell profit is
# better timewise than what we started with (O(n log n) versus O(n^2)), we can
# still improve the time performance. In particular, recall our recurrence
# relation:
#
# T(1) = O(1)
# T(n) = 2T(n / 2) + O(n)
#
# Here, the O(n) term in the T(n) case comes from the work being done to find
# the maximum and minimum values in the right and left halves of the array,
# respectively. If we could find these values faster than what we're doing
# right now, we could potentially decrease the function's runtime.
#
# The key observation here is that we can compute the minimum and maximum
# values of an array using a divide-and-conquer approach. Specifically:
#
# If the array has just one element, it is the minimum and maximum value.
# Otherwise:
# Split the array in half.
# Find the minimum and maximum values from the left and right halves.
# Return the minimum and maximum of these two values.
#
# Notice that our base case does only O(1) work, and our recursive case manages
# to do only O(1) work in addition to the recursive calls. This gives us the
# recurrence relation
#
# T(1) = O(1)
# T(n) = 2T(n / 2) + O(1)
#
# Using the Master Theorem, this solves to O(n).
#
# How can we make use of this result? Well, in our current divide-and-conquer
# solution, we split the array in half anyway to find the maximum profit we
# could make in the left and right subarrays. Could we have those recursive
# calls also hand back the maximum and minimum values of the respective arrays?
# If so, we could rewrite our solution as follows:
#
# If the array has size 1, the maximum profit is zero and the maximum and
# minimum values are the single array element.
# Otherwise:
# Split the array in half.
# Compute the maximum single-sell profit in the left array, call it L.
# Compute the maximum single-sell profit in the right array, call it R.
# Let Min be the minimum value in the left array, which we got from our
# first recursive call.
# Let Max be the maximum value in the right array, which we got from our
# second recursive call.
# Return the maximum of L, R, and Max - Min for the maximum single-sell
# profit, and the appropriate maximum and minimum values found from
# the recursive calls.
#
# The correctness proof for this algorithm works just as it did before, but now
# we never actually do a scan of the array at each step. In fact, we do only
# O(1) work at each level. This gives a new recurrence
#
# T(1) = O(1)
# T(n) = 2T(n / 2) + O(1)
#
# Which solves to O(n). We're now using O(n) time and O(log n) memory, which
# is asymptotically faster than before!
#
# The code for this is given below:
def OptimizedDivideAndConquerSingleSellProfit(arr):
# If the array is empty, the maximum profit is zero.
if len(arr) == 0:
return 0
# This recursive helper function implements the above recurrence. It
# returns a triple of (max profit, min array value, max array value). For
# efficiency reasons, we always reuse the array and specify the bounds as
# [lhs, rhs]
def Recursion(arr, lhs, rhs):
# If the array has just one element, we return that the profit is zero
# but the minimum and maximum values are just that array value.
if lhs == rhs:
return (0, arr[lhs], arr[rhs])
# Recursively compute the values for the first and latter half of the
# array. To do this, we need to split the array in half. The line
# below accomplishes this in a way that, if ported to other languages,
# cannot result in an integer overflow.
mid = lhs + (rhs - lhs) / 2
# Perform the recursion.
( leftProfit, leftMin, leftMax) = Recursion(arr, lhs, mid)
(rightProfit, rightMin, rightMax) = Recursion(arr, mid + 1, rhs)
# Our result is the maximum possible profit, the minimum of the two
# minima we've found (since the minimum of these two values gives the
# minimum of the overall array), and the maximum of the two maxima.
maxProfit = max(leftProfit, rightProfit, rightMax - leftMin)
return (maxProfit, min(leftMin, rightMin), max(leftMax, rightMax))
# Using our recursive helper function, compute the resulting value.
profit, _, _ = Recursion(arr, 0, len(arr) - 1)
return profit
# At this point we've traded our O(n^2)-time, O(1)-space solution for an O(n)-
# time, O(log n) space solution. But can we do better than this?
#
# To find a better algorithm, we'll need to switch our line of reasoning.
# Rather than using divide-and-conquer, let's see what happens if we use
# dynamic programming. In particular, let's think about the following problem.
# If we knew the maximum single-sell profit that we could get in just the first
# k array elements, could we use this information to determine what the
# maximum single-sell profit would be in the first k + 1 array elements? If we
# could do this, we could use the following algorithm:
#
# Find the maximum single-sell profit to be made in the first 1 elements.
# For i = 2 to n:
# Compute the maximum single-sell profit using the first i elements.
#
# How might we do this? One intuition is as follows. Suppose that we know the
# maximum single-sell profit of the first k elements. If we look at k + 1
# elements, then either the maximum profit we could make by buying and selling
# within the first k elements (in which case nothing changes), or we're
# supposed to sell at the (k + 1)st price. If we wanted to sell at this price
# for a maximum profit, then we would want to do so by buying at the lowest of
# the first k + 1 prices, then selling at the (k + 1)st price.
#
# To accomplish this, suppose that we keep track of the minimum value in the
# first k elements, along with the maximum profit we could make in the first
# k elements. Upon seeing the (k + 1)st element, we update what the current
# minimum value is, then update what the maximum profit we can make is by
# seeing whether the difference between the (k + 1)st element and the new
# minimum value is. Note that it doesn't matter what order we do this in; if
# the (k + 1)st element is the smallest element so far, there's no possible way
# that we could increase our profit by selling at that point.
#
# To finish up this algorithm, we should note that given just the first price,
# the maximum possible profit is 0.
#
# This gives the following simple and elegant algorithm for the maximum single-
# sell profit problem:
#
# Let profit = 0.
# Let min = arr[0]
# For k = 1 to length(arr):
# If arr[k] < min, set min = arr[k]
# If profit < arr[k] - min, set profit = arr[k] - min
#
# This is short, sweet, and uses only O(n) time and O(1) memory. The beauty of
# this solution is that we are quite naturally led there by thinking about how
# to update our answer to the problem in response to seeing some new element.
# In fact, we could consider implementing this algorithm as a streaming
# algorithm, where at each point in time we maintain the maximum possible
# profit and then update our answer every time new data becomes available.
#
# The final version of this algorithm is shown here:
def DynamicProgrammingSingleSellProfit(arr):
# If the array is empty, we cannot make a profit.
if len(arr) == 0:
return 0
# Otherwise, keep track of the best possible profit and the lowest value
# seen so far.
profit = 0
cheapest = arr[0]
# Iterate across the array, updating our answer as we go according to the
# above pseudocode.
for i in range(1, len(arr)):
# Update the minimum value to be the lower of the existing minimum and
# the new minimum.
cheapest = min(cheapest, arr[i])
# Update the maximum profit to be the larger of the old profit and the
# profit made by buying at the lowest value and selling at the current
# price.
profit = max(profit, arr[i] - cheapest)
return profit
# To summarize our algorithms, we have seen
#
# Naive: O(n ^ 2) time, O(1) space
# Divide-and-conquer: O(n log n) time, O(log n) space
# Optimized divide-and-conquer: O(n) time, O(log n) space
# Dynamic programming: O(n) time, O(1) space
关于arrays - 最大单笔销售利润,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7086464/
我的学校项目是创建一个销售和出租产品的电子商务网站。 我的主要问题是我找不到“出租”部分的最佳设计。现在我正在考虑两种设计: 第一个数据库设计建议: 第二条数据库设计建议: 如您所见,两种设计中都有相
如果 Mono 项目成功,它将为非 Windows 平台上的商业软件铺平道路。 我对根据我们现有的 Smoke Vector Graphics (OCaml) 和 F# for Visualizati
关闭。这个问题是off-topic .它目前不接受答案。 想改进这个问题吗? Update the question所以它是on-topic用于堆栈溢出。 关闭 10 年前。 Improve thi
关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。 这个问题似乎与 help center 中定义的范围内的编程无关。 . 关闭 8 年前。 Improve
是否有出售 .net 控件的网站?我似乎找不到任何东西。我想知道是否有人可以将我指向一个站点。我宁愿它不是一个需要提供源代码的网站(如果可以的话,无论如何都包括它们)。 最佳答案 有1个站点CodeC
免责声明:我主要是一名后端开发人员,没有广泛的 FE 知识。 我正在编写一个生成 HTML 的非 SPA Golang Web 应用程序,然后将其发送给用户。因为我想更好地更新和监控我的 Javasc
我尝试了几种不同的方法来从 Magento 中删除测试订单。 使用插件(http://www.magentocommerce.com/magento-connect/asperience-delete
我们有一个 Woocommerce 网站,并在 Facebook 和 Instagram 上转换广告。当潜在客户点击这些广告时,我们的网站将加载到 Facebook 和 Instagram 使用的应用
关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。 想改进这个问题?将问题更新为 on-topic对于堆栈溢出。 7年前关闭。 Improve this qu
我们已经在数据库中看到了销售数据,但在 Appstore Connect 控制台中看不到任何销售数据。有谁知道什么会导致这种情况吗? 只有当苹果应用内购买的 .purchased 状态回调被触发时,我
假设我有一个应用程序,我可以在其中以 iBook 的形式出售补充内容。无论哪种方式,他们都会收取 30%,但我可以将该应用程序用作销售它的平台。有没有一种方法可以通过应用程序本身销售它,但保留 iBo
我使用 BlueSnap API 通过 PayPal 销售产品。在我的网站上,我将购物者发送到 PayPal,而无需他们填写任何运输详细信息 - 一旦他们登录到 PayPal,我就会从他们的 Blue
最近,中国大型发行商联系了我,他们在越狱设备上拥有自己的“AppStore”。他们也让我通过他们的平台销售我的应用程序。我只是想知道有没有人有这方面的经验?合法吗? Apple 会在 AppStore
我正在尝试为 PayPal 交易提取 Sale Id。我正在使用 PayPalAndroidSDK 和 PayPal_MPL 到目前为止,我可以检索支付资源,例如PAY-... 使用这个: Paym
我已经安装了 Magento 2.2 并将支付方式配置为“PayPal Express Checkout” When i have payment with PayPal Express Checko
我有一个网站,人们可以在其中比较驾校。我已经使用 schema.org 标记将我知道的这些学校的所有详细信息(名称、描述、位置、价格范围等)添加到他们在我网站上的页面。 几周以来,人们还可以直接在我的
我需要知道一种向 magento admin 添加打印订单功能的方法。 最佳答案 您可以使用这个 extension .我没有测试它。于是手动安装。复制粘贴其扩展 key 并下载 here . 编辑:
我需要知道一种向 magento admin 添加打印订单功能的方法。 最佳答案 您可以使用这个 extension .我没有测试它。于是手动安装。复制粘贴其扩展 key 并下载 here . 编辑:
我有以下表格作为 MySQL Workbench 8.0CE 中更大架构的一部分; 订单 - Order_ID、Customer_ID、Payment_ID、Delivery_ID、Order_Dat
我正在使用亚马逊 MWS api 来获取完整的亚马逊订单列表。拥有这样的 api 非常好,它返回由亚马逊 (AFN) 完成和由卖家 (MFN) 订单完成。 登录到亚马逊卖家中心后,我可以看到所有销售
我是一名优秀的程序员,十分优秀!