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
121
122
123
124
125
#include "maklib.h"
#include "message.h"

#include <algorithm>
#include <iostream>
#include <assert.h>

using namespace std;

int get_from(int node)
{
	return (long long)Size() * (node  ) / NumberOfNodes() +1;
}

int get_to(int node)
{
	return (long long)Size() * (node+1) / NumberOfNodes();
}

int main()
{
	int from = get_from(MyNodeId());
	int to   = get_to(MyNodeId());

	long long mm = 0; // sum of max array starting no sooner than 'from', ending no further than 'from'
	long long f = 0;  // sum of elements from 'from', to i
	long long fm = 0; // sum of max array starting at 'from', ending no further than i
	long long fend;   // ending   index of max array starting at 'from', ending no further than i
	long long m = 0;  // sum of max array starting no sooner than 'from', ending at i
	long long start;  // starting index of max array starting no sooner than 'from', ending at i
	long long end;    // ending   index of max array starting no sooner than 'from', ending at i
	long long mstart; // starting index of max array starting no sooner than 'from', ending no further than i
	long long mend;   // ending   index of max array starting no sooner than 'from', ending no further than i

	start = mstart = from;
	end = fend = mend = from - 1;

	for(int i=from; i<=to; i++)
	{
		int e = ElementAt(i);
		f += e;
		if(f > fm)
		{
			fm = f;
			fend = i;
		}
		if(m + e > 0)
		{
			m = m + e;
			end = i;
		}
		else
		{
			m = 0;
			start = i + 1;
			end = i;
		}
		if(m > mm)
		{
			mm = m;
			mstart = start;
			mend = end;
		}
	}
	if(MyNodeId() > 0)
	{
		PutLL(0, fend);
		PutLL(0, fm);
		PutLL(0, f);
		PutLL(0, mm);
		PutLL(0, mstart);
		PutLL(0, mend);
		PutLL(0, start);
		PutLL(0, m);
		Send(0);
	}
	else
	{
		int nodes = NumberOfNodes();
		for (int node = 1; node < nodes; node++)
		{
			Receive(node);
			long long c_fend   = GetLL(node);
			long long c_fm     = GetLL(node);
			long long c_f      = GetLL(node);
			long long c_mm     = GetLL(node);
			long long c_mstart = GetLL(node);
			long long c_mend   = GetLL(node);
			long long c_start  = GetLL(node);
			long long c_m      = GetLL(node);

			if(mm < c_mm)
			{
				mm = c_mm;
				mstart = c_mstart;
				mend = c_mend;
			}
			if(mm < m + c_fm)
			{
				mm = m + c_fm;
				mstart = start;
				mend = c_fend;
			}
			if(c_m > m + c_f)
			{
				m = c_m;
				start = c_start;
			}
			else
			{
				m += c_f;
			}
		}
#if 0
		long long sum = 0;
		for(int i=mstart; i<=mend; i++)
		{
			sum += ElementAt(i);
		}
		assert(sum == mm);
#endif
		cout << mm << endl;
	}
	return 0;
}