# increasing sequences

• 03-09-2010
jack_carver
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
• 03-09-2010
karthigayan
post the code what you tried so far .
• 03-09-2010
itCbitC
post what you have done so far?
• 03-09-2010
jack_carver
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);```
• 03-09-2010
quzah
Vectors are C++. You're mixing your languages.

Quzah.