使用二分搜索找到具有最大和模 x 的子数组，我的解决方案使用迭代搜索。

Question

我正在处理 hackerrank.com 问题。基本前提给定一个数组A，和一个modulom，找到呈现最大值sum(B)%m的子数组B。所以给出最大子数组的子数组和modm是最大的。

我的基本方法是迭代处理每个子数组，并跟踪最大的总和。

我有两个问题：

如何用二进制搜索解决这个问题？我不明白如何在这里应用二进制搜索概念。
我当前的代码有什么问题。

感谢您的帮助。

# 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

Answer 1

首先，构造一个前缀（mod）和数组S，使得：

S[i] = sum(A[0..i]) % m

这可以使用以下关系在一次线性扫描中轻松完成：

S[0] = A[0] % m
S[i] = (S[i-1] + A[i]) % m

然而，当您构造此前缀和数组时，您还想找出“我可以使以 A[i] 结尾的最大 mod-sum 是多少？您已经知道 sum(A[0..i]) % m，也就是 S[i].

随便，sum(A[a..i]) % m对a > 0是什么？很简单：

(S[i] - S[a-1]) % m

如果您选择 a 这样 S[a-1] <= S[i]，您最终会得到 a 和 i 之间的 mod 总和，即小于（充其量等于）0和i之间的mod总和。

所以你必须选择 a 这样 S[a-1] > S[i]。如果存在这样的元素，S[i] - S[a-1] 将为负数。但是 (-x) % m == m - x 对于 x <= m。因此，我们希望以尽可能接近 0 的 x 结束。

换句话说，找到最小的 S[a-1]，对于0 < a < i，使得S[a-1] > S[i].

如果在计算 S[i] 元素并将其存储在前缀 (mod) 和数组中时，您维护了一个包含先前前缀和值的树，则可以执行搜索 "maximum mod-sum ending at element i" 在 O(lg n) 中使用二进制搜索方法。

当你这样做时，贪婪地 select 你看到的最大 mod-sum 值。

伪代码如下所示：

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

前缀和数组和树的运行时间应该在 O(n lg n) 中，O(n) space。

使用二分搜索找到具有最大和模 x 的子数组，我的解决方案使用迭代搜索。

Using Binary Search to find the sub array with the largest sum modulo x, my solution uses iterative search.

ruby

arrays

algorithm

binary-search