Advertisement
dim4o

Advanced_06_LongestNonDecreasingSubsequence

Apr 18th, 2014
221
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 2.53 KB | None | 0 0
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4.  
  5. namespace LongestNonDecreasingSubsequence
  6. {
  7.     class SeqList
  8.     {
  9.         static int equalsFirstIndex;
  10.         static int increasingFirstIndex;
  11.  
  12.         static void Main()
  13.         {
  14.             string input = Console.ReadLine();
  15.             input = input.Trim();
  16.             int[] arr = input.Split(' ').Select(s => int.Parse(s)).ToArray();
  17.             List<int> increasingSeq = getBestSequence(arr, false); //e.g:  1 2 3 4
  18.             List<int> equalSeq = getBestSequence(arr, true); //e.g:  1 1 1 1
  19.  
  20.             if (increasingSeq.Count < equalSeq.Count ||
  21.                 increasingSeq.Count == equalSeq.Count && increasingFirstIndex > equalsFirstIndex)
  22.             {
  23.                 increasingSeq = new List<int>(equalSeq);
  24.             }
  25.  
  26.             foreach (var item in increasingSeq)
  27.             {
  28.                 Console.Write(item + " ");
  29.             }
  30.             Console.WriteLine();
  31.         }
  32.         //finds longest non-decreasing subsequence
  33.         static List<int> getBestSequence(int[] arr, bool equal)
  34.         {
  35.             List<int>[] lens = new List<int>[arr.Length];
  36.             int maxIndex = 0;
  37.  
  38.             for (int currIndex = 0; currIndex < arr.Length; currIndex++)
  39.             {
  40.                 bool expression;
  41.                 lens[currIndex] = new List<int>();              
  42.                 lens[currIndex].Add(arr[currIndex]);
  43.                 for (int prevIndex = 0; prevIndex < currIndex; prevIndex++)
  44.                 {
  45.                     expression = arr[prevIndex] < arr[currIndex];
  46.                     if (equal == true)
  47.                     {
  48.                         expression = arr[prevIndex] == arr[currIndex];
  49.                     }
  50.                    
  51.                     if (expression &&
  52.                         lens[currIndex].Count <= lens[prevIndex].Count)
  53.                     {
  54.                         lens[currIndex] = new List<int>(lens[prevIndex]);
  55.                         lens[currIndex].Add(arr[currIndex]);
  56.  
  57.                         if (lens[currIndex].Count > lens[maxIndex].Count)
  58.                         {
  59.                             maxIndex = currIndex;
  60.                         }
  61.                     }
  62.                 }
  63.             }
  64.             if (equal == false)
  65.             {
  66.                 increasingFirstIndex = maxIndex;
  67.             }
  68.             else
  69.             {
  70.                 equalsFirstIndex = maxIndex;
  71.             }
  72.             return lens[maxIndex];
  73.         }
  74.     }
  75. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement