increasing sequences

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

post the code what you tried so far .

post what you have done so far?

Code:

---

                scanf("%d",&n);
                vector< pair<int,int> > sorted;
                for(int i=0;i<n;i++)
                {
                        scanf("%d",&num);
                        sorted.PB( make_pair(num,i) );
                }
                sort(sorted.begin(),sorted.end());

                int arr[MAX],cnt=1,ans=0;

                for(int i=0;i<n;i++)
                        arr[sorted[i].S]=cnt++;

                bool occur[MAX];memset(occur,0,sizeof occur);

                for(int i=0;i<n;i++)
                {
                        occur[arr[i]]=1;
                        if(occur[arr[i]-1])continue;
                        else ans++;
                }
                printf("#inc_seq = %d\n",ans);

---

Vectors are C++. You're mixing your languages.


Quzah.