我工作的一个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，阵列））＆GT; 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＆GT; 0
    test_cases_count = input_array [0]
其他
    respond_bad_input
结束

（1 ..（input_array.count-1））步骤（2）。每个做|首页|
    如果input_array.count-1＆GT;指数+ 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＆GT; 0 ？很简单，就是：

 （S [I]  -  S [A-1]）％M
 

如果您选择 A ，使得 S [A-1] = S [I] ，你会落得与 A 和我是小于的一个MOD-总和（充其量等于）之间的 0 mod森和我。

所以你必须选择 A ，使得 S [A-1]＆GT; S [I] 。如果这样的元素存在， S [I] - S [A-1] 将是负面的。但（ - X）％M ==米 - X 为 X＆LT; = M 。所以，我们要结束了 X 最接近 0 越好。

在换句话说，找到的最小的 S [A-1] 为 0℃ A＆LT;我，使得 S [A-1]＆GT; 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.