使用二进制搜索查找子阵列的最大的一笔模X,我的解决方案使用迭代搜索。 [英] Using Binary Search to find the sub array with the largest sum modulo x, my solution uses iterative search.
问题描述
我工作的一个hackerrank.com问题。基本premise给出一个数组 A
,和模 M
,找到子阵 B
呈现最大值和(B)%M
。因此,子阵列,让最大的子阵列总和mod M
是最大的。
我的基本方法是反复处理每个子阵列,并跟踪的最大的一笔。
我有两个问题:
-
我怎么能解决这个二进制搜索?我不明白怎么在这里应用二进制搜索概念。
-
什么是错我目前的code。
感谢您的帮助。
#https://www.hackerrank.com/challenges/maximise-sum
#接受输入
##
高清respond_bad_input
把坏投入。
结束
高清check_for_new_max(MOD,阵列,old_max)
(get_mod_sum(MOD,阵列))> old_max
结束
高清get_mod_sum(MOD,数组)
(array.inject {|总和,X |之和+ X})%MOD
结束
index_size = 0
index_modulo = 1
index_array = 2
test_cases_count = 0
test_cases = []
input_array = ARGF.to_a
如果input_array.count> 0
test_cases_count = input_array [0]
其他
respond_bad_input
结束
(1 ..(input_array.count-1))步骤(2)。每个做|首页|
如果input_array.count-1>指数+ 1
respond_bad_input
其他
大小= input_array [指数] .split()[0] .to_i
模数= input_array [指数] .split()[1] .to_i
test_array = input_array [索引+ 1] .split()
test_array.map {|!值| value.to_i}
test_cases.push([尺寸,模,test_array])
结束
结束
#运行每个测试用例
##
test_cases.each做| current_case |
MAX_VALUE = 0
current_case [index_array] .each_with_index办|价值,指数|
sub_array = [值]
如果check_for_new_max(current_case [index_modulo],sub_array,MAX_VALUE)
MAX_VALUE = get_mod_sum(current_case [index_modulo],sub_array)
结束
(指数。(current_case [index_array] .Count之间-1))各做|。sub_index |
sub_array = sub_array.push sub_index
如果check_for_new_max(current_case [index_modulo],sub_array,MAX_VALUE)
MAX_VALUE = get_mod_sum(current_case [index_modulo],sub_array)
max_array = sub_array
结束
结束
结束
把MAX_VALUE
结束
首先,构造一个preFIX(MOD)之阵,S,这样的:
S [I] = SUM(A [0..i])%M
这可以很容易地在一个线性扫描使用的关系做了:
S [0] = A [0]%M
S [I] =(S [I-1] + A [i]于)%间
当你构建这个preFIX之阵,不过,你也想弄清楚什么是最大的MOD-总和我可以与结束A [1]
?你已经知道和(A [0..i])%M
,这是 S [I]
。
随意,什么是和(A [a..i])%M
为 A> 0
?很简单,就是:
(S [I] - S [A-1])%M
如果您选择 A
,使得 S [A-1] = S [I]
,你会落得与 A
和我
是小于的一个MOD-总和(充其量等于)之间的 0
mod森和我
。
所以你必须选择 A
,使得 S [A-1]> S [I]
。如果这样的元素存在, S [I] - S [A-1]
将是负面的。但( - X)%M ==米 - X
为 X< = M
。所以,我们要结束了 X
最接近 0
越好。
在换句话说,找到的最小的 S [A-1]
为 0℃ A<我
,使得 S [A-1]> S [I]
。
如果,当你计算和存储你的 S [I]
在preFIX元素(MOD)之和数组,你维持previous一棵树preFIX和值,可以执行搜索最大模森在单元结束我
使用二进制搜索方法O(LG N)。
当你这样做,贪婪地选择最大MOD-和值,你看到的。
伪code是这样的:
输入:A,M
S:=初始化同样大小的preFIX数组作为数组A
S [0] = A [0]%M
max_mod_sum:= S [0]
T:=初始化一个空平衡树
对于i在[1,N):
S [I] =(S [I-1] + A [i]于)%间
max_ending_at_i:= S [I]
#寻找下一个,又名最小的数大于参数
prev_sum:= find_next(T,S [I])
如果prev_sum发现:
max_ending_at_i:=(S [I] - prev_sum)%间
max_mod_sum = MAX(max_mod_sum,max_ending_at_i)
插入(T,S [I])
回报max_mod_sum
运行时应该是为O(n LG N)与为preFIX总和数组,树O(n)的空间。
I'm working on a hackerrank.com problem. The basic premise is given an array A
, and a modulo m
, find the subarray B
that renders the largest value sum(B)%m
. So the sub array that gives the largest sub array which sum mod m
is the largest.
My basic approach is iteratively address every sub array, and keep track of the largest sum.
I have two questions:
How could I solve this with binary search? I don't understand how to apply the binary search concept here.
What is wrong with my current code.
Thanks for your help.
# https://www.hackerrank.com/challenges/maximise-sum
# Accept input
##
def respond_bad_input
puts "Bad input."
end
def check_for_new_max(mod, array, old_max)
(get_mod_sum(mod,array)) > old_max
end
def get_mod_sum(mod, array)
(array.inject{ |sum,x| sum + x }) % mod
end
index_size = 0
index_modulo = 1
index_array = 2
test_cases_count = 0
test_cases = []
input_array = ARGF.to_a
if input_array.count > 0
test_cases_count = input_array[0]
else
respond_bad_input
end
(1..(input_array.count-1)).step(2).each do |index|
if input_array.count-1 > index+1
respond_bad_input
else
size = input_array[index].split(" ")[0].to_i
modulo = input_array[index].split(" ")[1].to_i
test_array = input_array[index+1].split(" ")
test_array.map!{ |value| value.to_i }
test_cases.push([size, modulo, test_array ])
end
end
# Run each test case
##
test_cases.each do |current_case|
max_value = 0
current_case[index_array].each_with_index do |value, index|
sub_array = [value]
if check_for_new_max(current_case[index_modulo], sub_array, max_value)
max_value = get_mod_sum(current_case[index_modulo], sub_array)
end
(index..(current_case[index_array].count-1)).each do |sub_index|
sub_array = sub_array.push sub_index
if check_for_new_max(current_case[index_modulo], sub_array, max_value)
max_value = get_mod_sum(current_case[index_modulo], sub_array)
max_array = sub_array
end
end
end
puts max_value
end
First, construct a prefix (mod) sum array, S, such that:
S[i] = sum(A[0..i]) % m
This can easily be done in one linear scan using the relationship:
S[0] = A[0] % m
S[i] = (S[i-1] + A[i]) % m
As you construct this prefix sum array, however, you also want to find out "what is the maximum mod-sum I can make that ends with A[i]
? You already know sum(A[0..i]) % m
, which is S[i]
.
Arbitrarily, what is sum(A[a..i]) % m
for a > 0
? It is simply:
(S[i] - S[a-1]) % m
If you choose a
such that S[a-1] <= S[i]
, you'll end up with a mod-sum between a
and i
that is less than (at best, equal to) the mod-sum between 0
and i
.
So you'll have to pick a
such that S[a-1] > S[i]
. If such element exists, S[i] - S[a-1]
will be negative. But (-x) % m == m - x
for x <= m
. So, we want to end up with x
that is closest to 0
as possible.
In other words, find the smallest S[a-1]
, for 0 < a < i
, such that S[a-1] > S[i]
.
If, as you compute and store your S[i]
elements in the prefix (mod) sum array, you maintain a tree of previous prefix sum values, you can perform the search for "maximum mod-sum ending at element i
" in O(lg n) using binary search methods.
As you do this, greedily select the maximum mod-sum value you see.
The pseudo-code looks like this:
input: A, m
S := initialize a prefix array of the same size as array A
S[0] := A[0] % m
max_mod_sum := S[0]
T := initialize an empty self-balancing binary search tree
for i in [1, N):
S[i] = (S[i-1] + A[i]) % m
max_ending_at_i := S[i]
# finds the "next", aka smallest, number bigger than the argument
prev_sum := find_next(T, S[i])
if prev_sum is found:
max_ending_at_i := (S[i] - prev_sum) % m
max_mod_sum = max(max_mod_sum, max_ending_at_i)
insert(T, S[i])
return max_mod_sum
The runtime should be in O(n lg n) with O(n) space for the prefix sum array and tree.
这篇关于使用二进制搜索查找子阵列的最大的一笔模X,我的解决方案使用迭代搜索。的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!