# My Weblog

## Blog about programming and math

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 )

```

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