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
#include "message.h"
#include "maklib.h"
#include <iostream>
using namespace std;

int GetAt(int i) {
  static int size = Size();
  if(i>size) return ElementAt(size);
  if(i<1) return ElementAt(1);
  return ElementAt(i);
}

int intervalSum(int begin, int end, int breakPoint) {
  if(begin >= end) return 0;
  int sum = 0;
  for(int i=begin; i<end && (sum+breakPoint)>0 ; ++i) sum += GetAt(i);
  return sum;
}

int main() {
  int N = NumberOfNodes();
  int me = MyNodeId();
  int size = Size();
  //cout << "me " << me << endl;
  int begin = (size*me)/N+1;
  //cout << "begin " << begin << endl;
  int end = (size*(me+1))/N+1;
  if(end > (size+1)) end = size+1;
  //cout << "end " << end << endl;

  int maxArrayBegin, maxArrayEnd, maxSum = GetAt(begin);
  maxArrayBegin = begin;
  maxArrayEnd = begin+1;
  int totalSum = 0;

  for(int i = begin, arrayBegin = begin, arrayEnd = begin, sum = 0;
      i<end; ++i) {
    int n = GetAt(i);
    sum += n;
    totalSum += n;
    arrayEnd++;
    if(sum > maxSum) {
      maxSum = sum;
      maxArrayBegin = arrayBegin;
      maxArrayEnd = arrayEnd;
    }
    if(sum <= 0) {
      arrayBegin = arrayEnd = i+1;
      sum = 0;
    }
  }

  if(me > 0) {
    PutInt(0,maxSum);
    PutInt(0,maxArrayBegin);
    PutInt(0,maxArrayEnd);
    PutInt(0,totalSum);
    Send(0);
  } else {
    int sum = maxSum;
    int arrayBegin = maxArrayBegin;
    int arrayEnd = maxArrayEnd;
    for(int i=1; i<N; ++i) {
      Receive(i);
      int instSum = GetInt(i);
      int instArrayBegin = GetInt(i);
      int instArrayEnd = GetInt(i);
      int instTotalSum = GetInt(i);

      if(sum <= 0) {
	if(instSum < 0 && sum < instSum || instSum >= 0) {
	  sum = instSum;
	  arrayBegin = instArrayBegin;
	  arrayEnd = instArrayEnd;
	}
      } else {  //sum > 0
	if(arrayEnd == instArrayBegin) {
	  arrayEnd = instArrayEnd;
	  sum += instSum;
	} else {
	  int intermediateSum = intervalSum(arrayEnd, instArrayBegin, sum);
	  if((sum+intermediateSum) > 0) {
	    sum = sum+intermediateSum+instSum;
	    arrayEnd = instArrayEnd;
	  } else {
	    sum = instSum;
	    arrayBegin = instArrayBegin;
	    arrayEnd = instArrayEnd;
	  }
	}
      }

      if(sum > maxSum) {
	maxSum = sum;
	maxArrayBegin = arrayBegin;
	maxArrayEnd = arrayEnd;
      }

    }
    cout << maxSum << endl;
  }
}