Thread: increasing sequences

  1. #1
    Registered User
    Join Date
    Jan 2009
    Posts
    71

    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

  2. #2
    Registered User
    Join Date
    Nov 2008
    Location
    INDIA
    Posts
    64
    post the code what you tried so far .

  3. #3
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    post what you have done so far?

  4. #4
    Registered User
    Join Date
    Jan 2009
    Posts
    71
    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);

  5. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Vectors are C++. You're mixing your languages.


    Quzah.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C Escape sequences
    By Tool in forum C Programming
    Replies: 10
    Last Post: 11-20-2009, 09:38 PM
  2. Problem with Dynamically Increasing Array of Integers
    By laserlight in forum C++ Programming
    Replies: 30
    Last Post: 07-04-2008, 07:27 AM
  3. Sorting exam score in increasing order
    By superman12 in forum C Programming
    Replies: 5
    Last Post: 07-14-2005, 12:34 AM
  4. Using escape sequences as user inputs
    By musayume in forum C Programming
    Replies: 4
    Last Post: 12-11-2001, 09:35 AM
  5. ANSI Escape Sequences OR Scan of keyboard
    By Samppa in forum Linux Programming
    Replies: 3
    Last Post: 10-24-2001, 12:15 PM