Problem: ¶

An array is increasing if each element is less than its succeeding element except for the last element.

Given an array A of n elements return the beginning and ending indices of a longest increasing subarray of A.

Solution: ¶

Let S[i] be the longest increasing subarray between the indexes (0,i – 1). Then:

S[i] = a,b if A[i] > A[i – 1],
i,i otherwise
where a,b = S[i – 1]

In haskell this would be:

1longest_contig_inc_subarray :: (Ord a) => [a] -> (Int, Int)
2longest_contig_inc_subarray [] = (-1, -1)
3longest_contig_inc_subarray (x:xs) = longest_contig_inc_subarray' (0, x, 0, x) xs
4    where
5    longest_contig_inc_subarray' (i,ai,j,aj) [] = (i,j)
6    longest_contig_inc_subarray' (i,ai,j,aj) (x:xs)
7            | x >= aj = longest_contig_inc_subarray' (i,ai,j + 1,x) xs
8            | otherwise = longest_contig_inc_subarray' (j + 1,x,j + 1,x) xs

A heuristic to improve the best case complexity (but does nothing in the worst case) is to realise that if the length of the longest subarray till i is L (and A[i + 1] < A[i] – indicating an end of the longest subarray), then a larger increasing subarray must contain atleast L elements. So we only need to start with L items in front and check backwards.

The code for this is (here the start index and the length of the subarray are returned instead):

 1-- Returns the size of the largest increasing "prefix" in an array
 2largest_inc_prefix [] = 0
 3largest_inc_prefix (x:[]) = 1
 4largest_inc_prefix (x:y:xs)
 5        | x = y = 1 + largest_dec_prefix (y:xs)
 6        | otherwise = 1
 7
 8-- Returns the size of the largest decreasing "prefix" in an array
 9largest_dec_prefix [] = 0
10largest_dec_prefix (x:[]) = 1
11largest_dec_prefix (x:y:xs)
12        | x >= y = 1 + largest_dec_prefix (y:xs)
13        | otherwise = 1
14
15lcisa :: (Ord a) => [a] -> (Int, Int)
16lcisa [] = (-1,-1)
17lcisa xs = lcisa' (0,1) 0 xs
18    where
19        lcisa' (start,maxlen) i [] = (start,maxlen)
20        lcisa' (start,maxlen) i xs
21            | nextlen > maxlen = lcisa' nextbest
22                                    (i + maxlen + inc_prefix)
23                                    (drop inc_prefix rest)
24            | otherwise = lcisa' (start,maxlen) (i + maxlen) rest
25            where
26                first_l = take maxlen xs
27                rest = drop maxlen xs
28                dec_prefix = largest_dec_prefix (reverse first_l)
29                inc_prefix = largest_inc_prefix rest
30                nextlen = inc_prefix + dec_prefix
31                nextbest = (i + maxlen - dec_prefix, nextlen)