ruby - 如何分析数组中顺序数字的最大百分比增益(突发)？

Question

有一些算法可以检测数组中的最大子数组(连续的和非连续的)。不过，它们中的大多数都基于同时具有负数和正数。仅使用正数如何完成？

我有一个股票在相应时间范围内的值数组(比方说，该数组包含所有连续月份的值)。

[15.42, 16.42, 17.36, 16.22, 14.72, 13.95, 14.73, 13.76, 12.88, 13.51, 12.67, 11.11, 10.04, 10.38, 10.14, 7.72, 7.46, 9.41, 11.39, 9.7, 12.67, 18.42, 18.44, 18.03, 17.48, 19.6, 19.57, 18.48, 17.36, 18.03, 18.1, 19.07, 21.02, 20.77, 19.92, 18.71, 20.29, 22.36, 22.38, 22.39, 22.94, 23.5, 21.66, 22.06, 21.07, 19.86, 19.49, 18.79, 18.16, 17.24, 17.74, 18.41, 17.56, 17.24, 16.04, 16.05, 15.4, 15.77, 15.68, 16.29, 15.23, 14.51, 14.05, 13.28, 13.49, 13.12, 14.33, 13.67, 13.13, 12.45, 12.48, 11.58, 11.52, 11.2, 10.46, 12.24, 11.62, 11.43, 10.96, 10.63, 10.19, 10.03, 9.7, 9.64, 9.16, 8.96, 8.49, 8.16, 8.0, 7.86, 8.08, 8.02, 7.67, 8.07, 8.37, 8.35, 8.82, 8.58, 8.47, 8.42, 7.92, 7.77, 7.79, 7.6, 7.18, 7.44, 7.74, 7.47, 7.63, 7.21, 7.06, 6.9, 6.84, 6.96, 6.93, 6.49, 6.38, 6.69, 6.49, 6.76]

我需要一种算法来为每个元素确定它获得最大百分比增益的单个时间段。这可能是 1 个月的时间段、几个月的跨度或整个阵列(例如 120 个月)，具体取决于股票。然后我想根据百分比增益和返回(价格相对于原始价格的变化；因此峰值价格与该期间的起始价格)输出突发。

我结合了最大子数组类型的算法，但意识到这个问题有点不同；该数组没有负数，因此这些算法仅将整个数组报告为周期，将所有元素的总和报告为增益。

我提到的算法位于here和 here ，后者基于 Master Theorem .希望这会有所帮助。

我正在用 Ruby 编写代码，但也欢迎使用伪代码。

Answer 1

我认为你走错了路......
我不熟悉 ruby​​，但让我们用你自己的话在伪代码中构建算法:

I've got an array that contains the values of a stock over a range of time (let's say, for this example, each element is the value of the stock in a month; the array contains values for all consecutive months).

我们将这个数组命名为StockValues , 它的长度由 length(StockValues) 给出，假设它是基于 1 的(第一项是用 StockValues[1] 检索的)

I need an algorithm to analyze the array, and determine for each element the single time period where it had the biggest percentage gain in price.

您想知道给定索引 i在哪个指数 j与 j>i我们有最大的百分比 yield ，即当 gain=100*StockValues[j]/StockValues[i]-100 时是最大值。

I then want to output the burst, in terms of percentage gain, as well as the return(change in price over the original price; so the peak price vs the starting price in the period).

您想检索两个值 burst=gain=100*StockValues[j]/StockValues[i]-100和 return=StockValues[j]-StickValues[i]
第一步是遍历数组，并为每个元素做第二个循环以查找增益何时最大，当我们找到最大值时，我们将您想要的值保存在另一个名为 Result 的数组中(让我们假设该数组已初始化具有无效值，例如 burst=-1，这意味着在任何时间段内都找不到增益)

for i=1 to length(StockValues)-1 do
  max_gain=0
  for j=i+1 to length(StockValues) do
    gain=100*StockValues[j]/StockValues[i]-100
    if gain>max_gain then
      gain=max_gain
      Result[i].burst=gain
      Result[i].return=StockValues[j]-StockValues[i]
      Result[i].start=i
      Result[i].end=j
      Result[i].period_length=j-i+1
      Result[i].start_price=StockValues[i]
      Result[i].end_price=StockValues[j]
    end if
  end for
end for

注意这个算法给出的是最小周期，如果你替换gain>max_gain与 gain>=max_gain如果有多个周期具有相同的增益值，您将获得最长的周期。仅列出正增益或空增益，如果根本没有增益，结果将包含无效值。仅列出周期>1，如果接受周期 1，则最差增益可能为 0%，您将不得不修改循环 i转到 length(StockValues)和 j开始于 i