求一个序列中1占序列中比例最大的部分。

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

有这样一个有序序列是1和-1随机交互出现，我想求 1 在序列中占比最大的一段，并且求出它的百分比（为1的除以 1加上两侧挨着-1之和）。

举两个例子
序号    值
1         1
2         1
3        -1
4         1
5         1
6         1
7         1
8        -1
9        -1
10       1
那么这个之中 1 占比最大的序列是 3 到9  ，百分比为 4到7的1数量除以3 到9之和 为 4/7

第二个例子是为了解释为什么 每次遇到1 再重新相加求最大值方法行不通

序号     值
1          1
2         -1
3         -1
4          1
5          1
6          1
7          -1
8           1
9           1
10        -1

这个中的1 占最大比元素字段为2 到10 ，因为7后面有两个1 将抵消-1的影响， 百分比计算为 5/9

当然是有循环方法倒是可以实现，只不过稍微麻烦些。
麻烦各位有没有了解更好，更快的方法，谢谢！

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：最大的 百分比 有没有 最大值 最大的 百分比 最大值

你在讲啥

就是要求这个序列中，在某个位置开始到某个位置结束，这个为1的元素，占比最大。

题主的算法应该再描述清楚一些。你计算的两个比例里分母9是怎么得出的？

suimong 发表于 2015-12-19 18:46
题主的算法应该再描述清楚一些。你计算的两个比例里分母9是怎么得出的？

抱歉，第一个9应该为7，分子是1的数量，分母是1和两侧-1的数量之和。换句话说是，假如得到了某段元素中1最多，那么分子就是序列中1的数量，分母就是这段序列的总数量，也就是1和-1的数量之和。

序列中只有1和-1两种元素，思考解决方法时可以想成两种状态，百分比是为了衡量1这种元素在这段元素中的出现的强烈度。

也可以这么想，在1和-1的序列中，试图找到一段子序列，这段子序列中的元素满足一个假设:即在这段子序列元素中1和-1的数量差值最大.

ufuyu 发表于 2015-12-19 19:36
也可以这么想，在1和-1的序列中，试图找到一段子序列，这段子序列中的元素满足一个假设:即在这段子序列元素 ...

那为什么在例一里不是3：10呢？例二说明可以有不连续的两段1出现，那么在例一里3：9的比值是4/7，3：10的比值是5/8。而且如果你要求首尾都是-1的话那应该是3:8吧？

如果不考虑性能的话，你可以这么写：

1. library(lambda.tools)
   
2. D <- sample(c(1,-1), 50, replace = TRUE)
   
3. 
   
4. D_ratio <- lapply(seq_along(D), function(wsize) {
   
5.   maprange(D,wsize, function(x) {
   
6.     sum(x == 1) / (length(x) + 2)
   
7.   })
   
8. })
   
9. 
   
10. D_ratio_max <- sapply(D_ratio, max)
    
11. 
    
12. max_pos <- which.max(D_ratio[[which.max(D_ratio_max)]])
    
13. max_ratio <- D_ratio[[which.max(D_ratio_max)]][max_pos]

复制代码

这里我随机生成了一个长度为50的1,-1的序列。然后用长度为1，2，3...一直到50的窗口去扫描整个序列，并计算在每个窗口中1所占的比例（这里的比例是用1的数量除以整个窗口的长度+2，即相当于在窗口前后各加了一个-1），然后取出比值最大的那个值以及它所在的位置。