r - 优化 R 中的范围

Question

我有以下问题，不知道如何在 R 中编写代码:

具有两列的数据框 df:第一列是一组有序的数字 df$ind，第二列是一组高度随机的数字 df$ret 。

我想在 df$ret 中找到两个不重叠的范围，并优化条件，即第一个范围内的数字之和必须为正，第二个范围内的数字之和必须为正负范围。之后，我想要 2x2 df$ind-各自范围的值。

我想到了两种可能性(我不知道如何在 R 中对这两种可能性进行编程):

1. 选择 2x2 位置的 Monte Carlo，计算总和并与迄今为止的最佳解决方案进行比较。
2. 尝试所有可能的范围并采用最佳解决方案(关于值的数量，这在计算上似乎是可行的)。

你能给我一些提示，告诉我如何在 R 中实现这一点，或者是否有针对这些优化的包(似乎 R 中的所有内容都有一个包；-)

更新:
您将有 4 个值:i、k、m、n:df$ret[i :k] 和 df$ret[m:n] 与 i <k <m <n.

优化是(伪代码):

max:abs(sum(range(i:k)))+abs(sum(range(m:n)))

在条件下:

sum(range(i:k)) > 0 and sum(range(m:n)) < 0

Answer 1

这是一个蛮力方法。对于小数据集，它应该可以正常工作；在我的系统上，我测试了 100 号，大约是 0.5 秒。为了提高速度，应该在检查所有可能的最大/最小值对之前检查重叠的最佳最大值和最小值。

getbest <- function(x) {
  # get the sums of all possible ranges
  n <- length(x)
  m <- as.data.frame(t(combn(n, 2)))
  names(m) <- c("lo","hi")
  m$sum <- sapply(1:nrow(m), function(i) {
    sum(x[m$lo[i]:m$hi[i]])
  })
  # then get the ranges of positive and negative sums that don't overlap
  neg <- m[m$sum<0,]
  pos <- m[m$sum>0,]
  use <- expand.grid(neg=1:nrow(neg), pos=1:nrow(pos))
  use <- use[(neg$hi[use$neg] < pos$lo[use$pos]) | 
                  (neg$lo[use$neg] > pos$hi[use$pos]),]
  # finally get the absolute value for all ranges that don't overlap,
  # and choose the largest
  abs <- pos$sum[use$pos] - neg$sum[use$neg]
  use <- use[which.max(abs),]
  as.matrix(rbind(positive=pos[use$pos,], negative=neg[use$neg,]))
}

使用如下；它返回范围的实际索引，因此如果所需索引 df$ind 不同于 1:n，只需使用此输出来获取所需值。

x <- rnorm(100)
getbest(x)