SHARE
TWEET

Longest Non-decreasing Subsequence

Razhagal Mar 30th, 2014 127 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Threading.Tasks;
  6.  
  7. class LongestNonDecreasingSeq
  8. {
  9.     static void Main()
  10.     {
  11.         //Input
  12.         string input = Console.ReadLine();
  13.         //Split the elements into an array
  14.         string[] inputElements = input.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
  15.  
  16.         //Fill an integer array from string array
  17.         int[] elementsArray = new int[inputElements.Length];
  18.         for (int i = 0; i < inputElements.Length; i++)
  19.         {
  20.             elementsArray[i] = int.Parse(inputElements[i]);
  21.         }
  22.  
  23.         List<int> longestSequenceList = new List<int>();
  24.  
  25.         //Find the longest sequence of identical elements
  26.         int startIndex = 0;
  27.         int lenghtCount = 1;
  28.         int currentCount = 1;
  29.  
  30.         for (int i = 0; i < elementsArray.Length - 1; i++) //could start on index 1 and check current with previous elements
  31.         {
  32.             if (elementsArray[i] == elementsArray[i + 1])
  33.             {
  34.                 currentCount++;
  35.  
  36.                 if (currentCount > lenghtCount)
  37.                 {
  38.                     lenghtCount = currentCount;
  39.                     startIndex = (i + 1) - (lenghtCount - 1);
  40.                 }
  41.             }
  42.             else
  43.             {
  44.                 currentCount = 1;
  45.             }
  46.         }
  47.  
  48.         //Make the sequence currently longest
  49.         for (int i = 0; i < lenghtCount; i++)
  50.         {
  51.             longestSequenceList.Add(elementsArray[startIndex + i]);
  52.         }
  53.  
  54.         //Find how many combinations of sequences can be there
  55.         long combinations = 1;
  56.         for (int i = 0; i < elementsArray.Length; i++) //Instead of Math.Pow
  57.         {
  58.             combinations *= 2;
  59.         }
  60.        
  61.         for (long combination = 1; combination <= combinations; combination++)
  62.         {
  63.             //convert current combination number to its binary representation.
  64.             //That way we will use the positions with bit "1" with the elements on the same position in the array
  65.             string binary = Convert.ToString(combination, 2).PadLeft(elementsArray.Length, '0');
  66.             char[] tempArr = binary.ToCharArray();
  67.             Array.Reverse(tempArr);
  68.             string revBinary = new string(tempArr);
  69.  
  70.             List<int> tempList = new List<int>();
  71.             int bitsCount = 0;
  72.  
  73.             for (int i = 0; i < elementsArray.Length; i++)
  74.             {
  75.                 if (revBinary[i] == '1')
  76.                 {
  77.                     tempList.Add(elementsArray[i]);
  78.                     bitsCount++;
  79.                 }
  80.             }
  81.  
  82.             if (bitsCount < longestSequenceList.Count) //Speed optimisation
  83.             {
  84.                 continue;
  85.             }
  86.  
  87.             int currentLenght = 0;
  88.             List<int> currentLongestSeq = new List<int>();
  89.  
  90.             if (tempList.Count > 1) //Avoid cases where the current combination will use only 1 element
  91.             {
  92.                 int biggestNum = tempList[0];
  93.                 currentLongestSeq.Add(biggestNum);
  94.  
  95.                 for (int i = 0; i < tempList.Count - 1; i++)
  96.                 {
  97.                     //If the next number in the current combination sequence is bigger add it to final list
  98.                     if (tempList[i + 1] > biggestNum)
  99.                     {
  100.                         biggestNum = tempList[i + 1];
  101.  
  102.                         currentLongestSeq.Add(biggestNum);
  103.                     }
  104.                 }
  105.  
  106.                 currentLenght = currentLongestSeq.Count;
  107.             }
  108.  
  109.             if (currentLenght > longestSequenceList.Count)
  110.             {
  111.                 longestSequenceList = currentLongestSeq;
  112.             }
  113.         }
  114.  
  115.         //Output
  116.         for (int i = 0; i < longestSequenceList.Count; i++)
  117.         {
  118.             Console.Write(longestSequenceList[i] + " ");
  119.         }
  120.         Console.WriteLine();
  121.     }
  122. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top