実質的に大きい配列（複数のマシンにまたがる）で連続する整数の最大数を得る方法

Question

インタビューでこの質問がありました。最初の部分はかなりシンプルで、配列内の連続する整数の最大数を得るためのコードを書く必要がありました。

どのようにこのロジックを変更します複数のマシンに保存されている配列のために働くために：

int count = 0, max = 0; 
for(int i = 1; i < array.length; i++) { 
    if((array[i - 1] + 1) == array[i])) //curr is consecutive to prev 
      count++; 
    else 
      count = 0; //reset the counter as sequence is broken 

    //Keep track of maximum 
    if(count > max) 
     max = count; 
} 

System.out.println(max); //print the length of largest consecutive integers 

第二部がそれに質問をフォローアップだった：私が書いたコードを以下に示しますか？

Answer 1

あなたは（悪い、ネーミング・申し訳ありません）PythonでReduce Parallel Pattern

例を使用して、それを実装することができます

def longest_seq(seq): 

    Result = namedtuple("Result", ["left", "left_n", "max_n", "right", "right_n", "is_const"]) 

    def _longest_seq(seq): 
     if 1 == len(seq): 
      x = seq[0] 
      return Result(left=x, left_n=1, max_n=1, is_const=True, right=x, right_n=1) 

     l_res = _longest_seq(seq[0: int(len(seq)/2)]) 
     r_res = _longest_seq(seq[int(len(seq)/2): len(seq)]) 

     left_n = l_res.left_n + r_res.left_n if l_res.is_const and l_res.right == r_res.left else l_res.left_n 
     right_n = r_res.right_n + l_res.right_n if r_res.is_const and r_res.left == l_res.right else r_res.right_n 
     max_n = max(l_res.max_n, r_res.max_n, l_res.right_n + r_res.left_n if l_res.right == r_res.left else 0) 
     is_const = l_res.is_const and r_res.is_const and l_res.right == r_res.left 

     return Result(left=l_res.left, 
         left_n=left_n, 
         max_n=max_n, 
         right=r_res.right, 
         right_n=right_n, 
         is_const=is_const) 

    return _longest_seq(seq).max_n 

Answer 2

は、我々は全体の配列は、各マシンの順に左から右へ配布されていると仮定します。たとえば、2台のマシン（machine1とmachine2）の場合、0.... iをmachine1に、i + 1....nをmachine2に配付します。各マシンから、いくつかの追加情報をローカル最大値とともに返すことができます。そのmachineId連続している任意の二つのマシンのために、2機の結果をマージ中に

class result { 
    public int machineId; 
    public int maxSoFar; // the max value as your code 
    public int leftElement; // the leftmost element 
    public int leftLength; // number of times the leftElement appears consecutively in left 
    public int rightElement; // the rightmost element 
    public int rightLength; // number of times the rightElement appears consecutively in right 
}; 

（例えば3と4。）、我々は次のように最大化することができます -

return Math.max(((machine1.rightElement == machine2.leftElement) ? machine1.rightLength + machine2.leftLength : 0), 
        Math.max(machine1.maxSoFar, machine2.maxSoFar));