0

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

我在一个连续的时间范围内有一组股票的值（比如说，该数组包含所有连续月份的值）。

[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 个月），具体取决于库存。然后，我想以百分比增益以及回报（价格相对于原始价格的变化；因此该期间的峰值价格与起始价格）来输出爆发。

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

我提到的算法位于此处和此处，后者基于主定理。希望这可以帮助。

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

4

2 回答 2

2

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

我有一个数组，其中包含某个时间范围内的股票值（假设对于这个示例，每个元素都是一个月内的股票值；该数组包含所有连续月份的值）。

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

我需要一种算法来分析数组，并为每个元素确定价格涨幅最大的单个时间段。

您想知道对于给定索引，我们i在哪个索引处获得最大百分比增益，即何时最大。jj>igain=100*StockValues[j]/StockValues[i]-100

然后，我想以百分比增益以及回报（价格相对于原始价格的变化；因此该期间的峰值价格与起始价格）来输出爆发。

您要检索这两个值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仅列出正增益或空增益，如果根本没有增益，则结果将包含无效值。仅列出 period>1，如果接受 1 的周期，则可能的最差增益为 0%，您必须修改循环i转到length(StockValues)并j开始于i

于 2012-09-19T00:08:49.767 回答
1

这听起来不像是几天的工作：p 除非我错过了什么。

# returns array of percentage gain per period
def percentage_gain(array)
  initial = array[0]
  after = 0
  percentage_gain = []
  1.upto(array.size-1).each do |i|
    after = array[i]
    percentage_gain << (after - initial)/initial*100
    initial = after
  end
  percentage_gain
end

# returns array of amount gain $ per period
def amount_gain(array)
  initial = array[0]
  after = 0
  amount_gain = []
  1.upto(array.size-1).each do |i|
    after = array[i]
    percentage_gain << (after - initial)
    initial = after
  end
  amount_gain
end

# returns the maximum amount gain found in the array
def max_amount_gain(array)
  amount_gain(array).max
end

# returns the maximum percentage gain found in the array
def max_percentage_gain(array)
  percentage_gain(array).max
end

# returns the maximum potential gain you could've made by shortselling constantly.
# i am basically adding up the amount gained when you would've hit profit.
# on days the stock loses value, i don't add them.
def max_potential_amount_gain(array)
  initial = array[0]
  after = 0
  max_potential_gain = 0
  1.upto(array.size-1).each do |i|
    after = array[i]
    if after - initial > 0
      max_potential_gain += after - initial
    end
    initial = after
  end
  amount_gain
end

array = [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]
于 2012-09-19T00:09:46.617 回答