## 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

No comments yet.

## Leave a Reply