1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include "message.h"
#include "maklib.h"

#include <algorithm>
#include <iostream>
using namespace std;

int main() {
  int n = Size();
  int idx = MyNodeId();
  int nodes = NumberOfNodes();
  int start_idx = n * idx / nodes;
  int end_idx = n * (idx + 1) / nodes;

  long long left_max = 0;
  long long sum = 0;
  long long currZeroSum = 0;
  long long maxZeroSum = 0;

  for (int i = start_idx; i < end_idx; i++) {
    long long elem = ElementAt(i+1);
    sum += elem;
    if (sum > left_max) {
      left_max = sum;
    }
    currZeroSum += elem;
    if (currZeroSum < 0) {
      currZeroSum = 0;
    }
    if (currZeroSum > maxZeroSum) {
      maxZeroSum = currZeroSum;
    }
  }

  // cout << left_max << " " << sum << " " << currZeroSum << " " << maxZeroSum << endl;

  if (idx < nodes - 1) {
    Receive(idx + 1);
    long long right_left_max = GetLL(idx + 1);
    long long right_max_zero_sum = GetLL(idx + 1);

    left_max = max(left_max, sum + right_left_max);
    maxZeroSum = max(maxZeroSum, max(right_max_zero_sum, currZeroSum + right_left_max));
  }
  if (idx > 0) {
    PutLL(idx - 1, left_max);
    PutLL(idx - 1, maxZeroSum);
    Send(idx - 1);
  }
  if (idx == 0) {
    cout << maxZeroSum << endl;
  }

  return 0;
}