!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!  Solution to the Maximum Subarray  !
!  Problem using brute force and     !
!  linear time solutions             !
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!  The Maximum Subarray Problem consists of  !!
!!  finding within a set of numbers a subset  !!
!!  with the largest sum.  Implemented here   !!
!!  are 2 solutions:  a brute force solution  !!
!!  running in O(n^2) time and Kadane's       !!
!!  solution running in O(n) time.            !!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!  compiled with gfortran -fdefault-real-8 max_sub_mod.f95 max_sub.f95  !!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!  ABW 2012-2015  !
!!!!!!!!!!!!!!!!!!!
program maxsub
  use max_sub_mod
  implicit none
  
  integer :: i  
  integer,parameter :: n1 = 5
  integer,dimension(n1) :: array1
  integer,parameter :: n2 = 16
  integer,dimension(n2) :: array2
  integer,parameter :: n3 = 10000
  real(kind=8),dimension(n3) :: array3
  real(kind=8) :: time,hold

  call init_rand_seed()
  
  !  Just make up some values for a simple test:
  data (array1(i),i=1,n1)/-4,1,5,-1,3/
  !  The maximum subarray is from element 2 to element 5
  
  !  A 16 element array test:
  data (array2(i),i=1,n2)/13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7/
  !  The maximum subarray is between elements 8 and 11
  
  !  A 10000 element real array:
  do i = 1,n3
     call random_number(hold)
     array3(i) = 100*hold
     !  With a probability of 50%, each element is made negative
     if(hold > 0.5) then  
        array3(i) = -1.0*array3(i)
     endif
  enddo  
  
  write(*,*) '=====================Using  Kadane====================='
  write(*,*) 'For the 5 element array:'
  call ilinmax(array1,n1)
  write(*,*)
  write(*,*) 'For the 16 element array:'
  call ilinmax(array2,n2)  
  write(*,*)
  write(*,*) 'For the 10,000 element array:'
  call rlinmax(array3,n3)
  write(*,*)
  call cpu_time(time)
  write(*,"(A,F22.16,A)") 'CPU Time:', time, ' seconds'
  write(*,*)
  
  write(*,*) '===================Using Brute Force==================='
  write(*,*) 'For the 5 element array:'
  call ibrute(array1,n1)
  write(*,*)
  write(*,*) 'For the 16 element array:'
  call ibrute(array2,n2)  
  write(*,*)
  write(*,*) 'For the 10,000 element array:'
  call rbrute(array3,n3)
  write(*,*)
  call cpu_time(time)
  write(*,"(A,F22.16,A)") 'CPU Time:', time, ' seconds'
  
contains

  subroutine init_rand_seed()
    integer,dimension(:),allocatable :: seed
    integer :: i,nr
    
      call random_seed(size=nr)
      allocate(seed(nr))
      do i = 1,nr
	 seed(i) = 102
      enddo
      call random_seed(put = seed)
      deallocate(seed)
  end subroutine init_rand_seed
end program maxsub
