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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <assert.h>
#include <inttypes.h>
#include <stdio.h>
#include "maklib.h"
#include "message.h"

#define MIN(a, b) ((a) <= (b) ? (a) : (b))
#define MAX(a, b) ((a) >= (b) ? (a) : (b))


long long join_partitions()
{
    long long the_best = 0;
    long long current = 0;
    int i;
    for (i = 0; i < NumberOfNodes(); i++)
    {
        Receive(i);
        long long head = GetLL(i);
        long long total = GetLL(i);
        long long tail = GetLL(i);
        long long best = GetLL(i);
        long long candidate;
        candidate = current + head;
        the_best = MAX(the_best, candidate);
        candidate = current + total;
        current = MAX(candidate, tail);
        the_best = MAX(the_best, current);
        the_best = MAX(the_best, best);
    }
    return the_best;
}

void process_partition(int begin, int end)
{
    // Compute
    long long head = 0;
    long long total = 0;
    long long tail = 0;
    long long best = 0;
    long long current_head = 0;
    long long current_tail = 0;
    int i = 0;

    for (i = begin; i <= end; i++)
    {
        int x = ElementAt(i);
        current_head += x;
        head = MAX(head, current_head);
        total += x;
        long long candidate = current_tail + x;
        current_tail = MAX(candidate, 0);
        best = MAX(best, current_tail);
    }
    tail = current_tail;

    PutLL(0, head);
    PutLL(0, total);
    PutLL(0, tail);
    PutLL(0, best);
    Send(0);
}

int main()
{
    if (MyNodeId() == 0) {
        fprintf(stderr, "Size: %d, Nodes: %d\n", Size(), NumberOfNodes());
    }
    int nodes = NumberOfNodes();
    int size = Size();
    int begin = (MyNodeId() * size) / nodes + 1;
    int end = ((MyNodeId() + 1) * size) / nodes;
    fprintf(stderr, "Partition %d: [%d, %d]\n", MyNodeId(), begin, end);
    process_partition(begin, end);
    if (MyNodeId() == 0) {
        long long the_best = join_partitions();
        printf("%lld\n", the_best);
    } 
    return 0;
}