Does any 1 know an easy way to count the number of increasing sequences in an array ?
ex: 1 5 2 6 3 7 4 8
ans is 2 -> [1,2,3,4] , [5,6,7,8]
ex: 1 3 5 2 4 6
ans is 3 -> [1,2] , [3,4] , [5,6]
ex: 4 3 2 1
ans is 4 -> [4] , [3] , [2] , [1]
ex: 1 2 3 4 6 5
ans is 2 -> [1,2,3,4,5] , [6]
ex: 1 2 3 1 2 2
ans is 2 -> [1,1,2,2] , [2,3]
I am unable to do it for cases of the last category i.e, when there are repeating elements ? .. Does any 1 have any idea ? ..even a small hint would do
EDIT: O(nlgn) is required :P
Thanks