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
126
// Rafał Jankowski @ Potyczki Algorytmiczne 2014
#include <iostream>
#include "maklib.h"
#include "message.h"

using namespace std;

typedef long long LL;

// Algorytm Kadane

// |:::::preSumZ]preSumW][sum][postSumW[postSumZ:::::|

class Process {
	private:
		int rangeBegin;
		int rangeEnd;
		int begin;
		int end;
		LL maxn;
		LL sum;
		void greater( const int& );
		void addElem( const int& , const int& );
		void lowerZero( const int& );
	public:
		Process( const int & , const int& );
		const int getRangeBegin();
		const int getRangeEnd();
		const int getBegin();
		const int getEnd();
		void kadane();
		const LL getSum();
};

Process::Process( const int &start , const int &end ) {
	this->rangeBegin = start;
	this->rangeEnd = end;
	this->maxn = 0;
	this->sum = 0;
	this->begin = start;
	this->end = start;

	//Run Kadane Algorithm
	this->kadane();
}

const int Process::getRangeBegin() {
	return (this->rangeBegin);
}

const int Process::getRangeEnd() {
	return (this->rangeEnd);
}

void Process::greater( const int& pos ) {
	if( this->sum > this->maxn ) {
		this->maxn = this->sum;
		this->end = pos;
	}
}

void Process::lowerZero( const int& pos ) {
	if( this->sum < 0 ) {
		this->sum = 0;
		this->begin = pos+1;
	}
}

void Process::addElem( const int& newElem , const int& it ) {
	this->sum += newElem;
	this->greater( it );
	this->lowerZero( it );
}

const LL Process::getSum() {
	return (this->maxn);
}

const int Process::getBegin() {
	return (this->begin);
}

const int Process::getEnd() {
	return (this->end);
}

void Process::kadane() {
	for( int it = this->getRangeBegin(); it <= this->getRangeEnd() && it <= Size(); it++ ) {
		this->addElem( ElementAt( it ) , it );
	}
}

int main() {
	const int PARSESIZE = Size()/NumberOfNodes() + ( Size() % NumberOfNodes() > 0 );
	const int BEGIN = PARSESIZE*MyNodeId()+1;
	//Process * qProcess = new Process( BEGIN , PARSESIZE*(MyNodeId()+1) );
	Process * qProcess = new Process( BEGIN , Size() );

	if( MyNodeId() != 0 ) {
		//Child Node
		PutLL( 0 , qProcess->getSum() );
		PutInt( 0 , qProcess->getBegin() );
		PutInt( 0 , qProcess->getEnd() );
		Send( 0 );
	}
	else {
		//Root Node
		int begin=qProcess->getBegin(), end=qProcess->getEnd(), nBegin, nEnd; LL sum = qProcess->getSum(), nSum, preSum, postSum;
		/*for( int i = 1; i < NumberOfNodes(); i++ ) {
			Receive( i );
			nSum = GetLL( i );
			nBegin = GetInt( i );
			nEnd = GetInt( i );
			preSum = postSum = 0;
			//cout << nSum << endl;
			Process * nProcess = new Process( end+1 , nBegin-1 );
			for( int j = end+1; j <= nProcess->getBegin()-1; j++ )
				preSum += ElementAt( j );
			for( int j = nProcess->getEnd()+1; j <= nBegin-1; j++ )
				postSum += ElementAt( j );
		}*/
		cout << sum << endl;
	}

	return 0;
}