• API
• FAQ
• Tools
• Archive
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;
6.
7. class LongestNonDecreasingSeq
8. {
9.     static void Main()
10.     {
11.         //Input
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.         {
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.                 {
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;
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.
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.

Top