module Task
  use :: mpi
  implicit none
  contains

  subroutine GetMaxCoordinates(A, x1, y1, x2, y2)
    implicit none
    integer(4), intent(out) :: x1, y1, x2, y2
    integer(4) :: n, L, R, Up, Down, m,  new_x1, new_x2, new_y1, new_y2, calls
    real(8), intent(in), dimension(:,:) :: A
    real(8), allocatable :: current_column(:)
    real(8) :: current_sum, max_sum, new_sum

    integer(4) :: mpiErr, mpiRank, mpiSize
    integer(4), dimension(MPI_STATUS_SIZE) :: status

    m = size(A, dim=1)
    n = size(A, dim=2)

    allocate(current_column(m))

    x1=1
    y1=1
    x2=1
    y2=1
    max_sum = A(1,1)

    call MPI_Comm_size(MPI_COMM_WORLD, mpiSize, mpiErr)
    call MPI_Comm_rank(MPI_COMM_WORLD, mpiRank, mpiErr)

    do L = mpiRank+1, n, mpiSize
      current_column = A(:, L)
      do R = L, n
        if (R .gt. L) then
          current_column = current_column + A(:, R)
        endif

        call FindMaxInArray(current_column, current_sum, Up, Down)

        if (current_sum .gt. max_sum) then
          max_sum = current_sum
          x1 = Up
          x2 = Down
          y1 = L
          y2 = R
        endif

      end do
    end do

    if (mpiRank /= 0) then
      call MPI_Send(max_sum, 1, MPI_REAL8, 0, mpiRank+mpiSize, MPI_COMM_WORLD, mpiErr)
      call MPI_Send(x1, 1, MPI_INTEGER4, 0, mpiRank+mpiSize, MPI_COMM_WORLD, mpiErr)
      call MPI_Send(x2, 1, MPI_INTEGER4, 0, mpiRank+mpiSize, MPI_COMM_WORLD, mpiErr)
      call MPI_Send(y1, 1, MPI_INTEGER4, 0, mpiRank+mpiSize, MPI_COMM_WORLD, mpiErr)
      call MPI_Send(y2, 1, MPI_INTEGER4, 0, mpiRank+mpiSize, MPI_COMM_WORLD, mpiErr)
    else
    calls = 0
    do while (calls /= mpiSize-1)
      call MPI_Recv(new_sum, 1, MPI_REAL8, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, status, mpiErr)
      call MPI_Recv(new_x1, 1, MPI_INTEGER4, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, status, mpiErr)
      call MPI_Recv(new_x2, 1, MPI_INTEGER4, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, status, mpiErr)
      call MPI_Recv(new_y1, 1, MPI_INTEGER4, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, status, mpiErr)
      call MPI_Recv(new_y2, 1, MPI_INTEGER4, MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, status, mpiErr)
      calls = calls + 1

      if (new_sum .gt. max_sum) then
        max_sum = new_sum
        x1 = new_x1
        x2 = new_x2
        y1 = new_y1
        y2 = new_y2
       endif
    enddo
    endif

    call MPI_Bcast(x1, 1, MPI_INTEGER4, 0, MPI_COMM_WORLD, mpiErr)
    call MPI_Bcast(x2, 1, MPI_INTEGER4, 0, MPI_COMM_WORLD, mpiErr)
    call MPI_Bcast(y1, 1, MPI_INTEGER4, 0, MPI_COMM_WORLD, mpiErr)
    call MPI_Bcast(y2, 1, MPI_INTEGER4, 0, MPI_COMM_WORLD, mpiErr)

    deallocate(current_column)
  end subroutine

  subroutine FindMaxInArray(A, Summ, Up, Down)
    implicit none
    real(8), intent(in), dimension(:) :: A
    integer(4), intent(out) :: Up, Down
    real(8), intent(out) :: Summ
    real(8) :: cur_sum
    integer(4) :: minus_pos, i

    Summ = A(1)
    Up = 1
    Down = 1
    cur_sum = 0
    minus_pos = 0

    do i=1, size(A)
      cur_sum = cur_sum + A(i)
      if (cur_sum .gt. Summ) then
        Summ = cur_sum
        Up = minus_pos + 1
        Down = i
      endif

      if (cur_sum .lt. 0) then
        cur_sum = 0
        minus_pos = i
      endif
    enddo

  end subroutine

end module