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
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
/*
 *  Copyright (C) 2014  Paweł Widera
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details:
 *  http://www.gnu.org/licenses/gpl.html
 */
#include "maklib.h"
#include "message.h"

#include <tuple>
#include <cmath>
#include <iostream>
using namespace std;


tuple<long long int, int, int> find_max_sum(int a, int b) {
	long long int max_sum = 0;
	long long int sum = 0;
	int begin = a;
	int end = b;

	//cout << "a,b " << a << " " << b << endl;

	for (auto i = a; i < b; ++i) {
		if (sum > 0) {
			sum += ElementAt(i);
		} else {
			sum = ElementAt(i);
			begin = i;
		}
		if (sum > max_sum) {
			max_sum = sum;
			end = i + 1;
		}
	}

	// enable skipping the fragment if all numbers are negative
	if (0 == max_sum) {
		begin = end;
	}

	return make_tuple(max_sum, begin, end);
}


int main() {
	int fragment_size = ceil(Size() / float(NumberOfNodes()));
	long long int max_sum;
	int begin;
	int end;

	tie(max_sum, begin, end) = find_max_sum(MyNodeId() * fragment_size + 1,
		min((MyNodeId() + 1) * fragment_size + 1, Size() + 1));

	//cout << max_sum << " " << begin << "," << end << endl;

	if (MyNodeId() > 0) {
		PutLL(0, max_sum);
		PutInt(0, begin);
		PutInt(0, end);
		Send(0);
	} else {
		auto sum = max_sum;

		for (int k = 1; k < NumberOfNodes(); ++k) {
			Receive(k);
			auto next_max_sum = GetLL(k);
			auto next_begin = GetInt(k);
			auto next_end = GetInt(k);

			//cout << "merge " << next_begin << "," << next_end << endl;

			// merge current and next fragment
			for (int i = end; i < next_begin; ++i) {
				if (sum > 0) {
					sum += ElementAt(i);
				} else {
					// skip if all numbers in the fragment are negative
					if (0 == next_max_sum) {
						break;
					} else {
						sum = ElementAt(i);
					}
				}
				if (sum > max_sum) {
					max_sum = sum;
				}
			}

			//cout << "merge sum = " << sum << endl;

			if (sum > 0) {
				sum += next_max_sum;
			} else {
				sum = next_max_sum;
			}
			if (sum >= max_sum) {
				max_sum = sum;
			}

			//cout << "merge max_sum = " << max_sum << endl;

			end = next_end;
		}

		if (max_sum < 0) {
			max_sum = 0;
		}
		cout << max_sum << endl;
	}
	return 0;
}