My Weblog

Blog about programming and math

Kadane’s Algorithm

According to wiki “the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers (containing at least one positive number) which has the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6”. My Haskell implementation for Kadane’s algorithm. This program returns maximum sum of array , starting index [inclusive ] and last index [exclusive ] of sub array .This site also explains this algorithm quite nicely.

import qualified Data.List as L 
import Data.Bits

kadaneAlgo :: [Integer] -> ( Integer , Int , Int )
kadaneAlgo xs = kadaneHelper xs 0 0 0 0 0  0 where      
        kadaneHelper [] maxSum _  _ fStart fEnd _ = ( maxSum , fStart , fEnd )
	kadaneHelper ( y:ys ) maxSum maxStart maxEnd fStart fEnd currSum =  
		case ( currSum + y > maxSum ) of 
			True -> kadaneHelper ys ( currSum + y) maxStart ( maxEnd + 1) maxStart  ( maxEnd + 1 ) ( currSum + y ) 
			_    -> case ( currSum + y < 0 ) of 
				  True -> kadaneHelper ys maxSum ( maxEnd + 1 ) ( maxEnd + 1 ) fStart  fEnd  0
				  _    -> kadaneHelper ys maxSum maxStart  ( maxEnd + 1 )  fStart fEnd ( currSum + y )
		
		



main = interact $ show.kadaneAlgo.map read.words

The same code using foldl function. If you find any error then please let me know .

import Data.List


kadane :: [Integer] -> ( Integer , Int , Int )
kadane xs = ( sum , sIndex , eIndex ) where
	    ( sum , _ , _ , _ , sIndex , eIndex ) = 
		foldl ( \ ( mSum , cSum , sInd , eInd , sFin , eFin ) x -> if ( cSum + x > mSum ) then ( cSum + x , cSum + x , sInd , eInd + 1 , sInd , eInd + 1 ) 
									    else  
									      if ( cSum + x < 0 ) then ( mSum , 0 , eInd + 1 , eInd + 1 , sFin , eFin ) 
									       else ( mSum , cSum + x , sInd , eInd + 1, sFin , eFin  )  ) ( 0 , 0 , 0 , 0 , 0 , 0 ) xs
Advertisements

May 12, 2011 - Posted by | Programming

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: