!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!  Module that holds the real and   !
!  integer subroutines for brute    !
!  force and linear time solutions  !
!  to the Maximum Subarray Problem  !
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
module max_sub_mod
  implicit none
  
contains
  
  !  Brute force method for real arrays
  subroutine rbrute(Array,n)
    integer :: n
    real(kind=8),dimension(n) :: Array
    integer :: i,j,k,left,right
    real(kind=8) :: small,s
    
    small = -100000000.0
    do i=1,n
       do j=i,n
          s=0.0
          do k=i,j
             s = s + Array(k)           
             if(s > small) then
                small = s
                left = i
                right = k
             endif
          enddo
       enddo
    enddo
    write(*,101) ' The Maximum Subarray is from elements',left,' to',right,' and sums to',small,'.'
101 format (A,I5.1,A,I5.1,A,F12.5,A)
  end subroutine rbrute
  
  !  Brute force method for integer arrays
  subroutine ibrute(Array,n)
    integer :: n
    integer,dimension(n) :: Array
    integer :: i,j,k,s,small,left,right
    
    small = -100000000
    do i=1,n
       do j=i,n
          s=0
          do k=i,j
             s = s + Array(k)          
             if(s > small) then
                small = s
                left = i
                right = k
             endif
          enddo
       enddo
    enddo
    write(*,102) ' The Maximum Subarray is from elements',left,' to',right,' and sums to',small,'.'
102 format (A,I2.1,A,I3.1,A,I3.1,A)
  end subroutine ibrute
  
  !  Kadane's Algorithm for real arrays
  subroutine rlinmax(Array,n)
    implicit none
    integer :: n
    real(kind=8),dimension(n) :: Array
    integer :: i,j,k,left,right
    real(kind=8) :: h,s
    
    h = 0.0
    s = 0.0
    left = 1
    j = 0
    do i = 1,n      
       h = h + Array(i)
       if(h < 0) then
          h = 0.0
          j = i+1
       endif
       if(h > s) then
          s = h
          right = i
          left = j
       endif
    enddo
    write(*,103) ' The Maximum Subarray is from elements',left,' to',right,' and sums to',s,'.'
103 format (A,I5.1,A,I5.1,A,F12.5,A)
  end subroutine rlinmax
  
  !  Kadane's Algorithm for integer arrays
  subroutine ilinmax(Array,n)
    implicit none
    integer :: n
    integer,dimension(n) :: Array
    integer :: i,j,k,h,s,left,right
    
    h = 0
    s = 0
    left = 1
    j = 0
    do i = 1,n       
       h = h + Array(i)
       if(h < 0) then
          h = 0
          j = i+1
       endif
       if(h > s) then
          s = h
          right = i
	  left = j
       endif
    enddo
    write(*,104) ' The Maximum Subarray is from elements',left,' to',right,' and sums to',s,'.'
104 format (A,I2.1,A,I3.1,A,I3.1,A)
  end subroutine ilinmax
  
end module max_sub_mod
