Untitled

mail@pastecode.io avatar
unknown
csharp
a month ago
2.0 kB
4
Indexable
Never
using System;

class Program
{
    const int MaxN = 1000; // Maximum number of numbers
    static int[] A = new int[MaxN + 1]; // Given sequence of numbers
    static int[] B = new int[MaxN + 1]; // Length of the longest non-decreasing subsequence
    static int[] C = new int[MaxN + 1]; // Length of the longest subsequence with exactly one decrease
    static int N; // Number of numbers
    static int V; // Resulting length of the longest subsequence
    static void Main()
    {
        Console.Write("Počet čísel: ");
        N = int.Parse(Console.ReadLine());
        if (N == 0)
        {
            V = 0;
        }
        else
        {
            Console.WriteLine("Posloupnost čísel:");
            for (int i = 1; i <= N; i++)
            {
                A[i] = int.Parse(Console.ReadLine());
                B[i] = 1;
                C[i] = 0;
            }
            V = 1;
        }

        for (int i = N - 1; i >= 1; i--) // Determining values B[i], C[i]
        {
            for (int j = i + 1; j <= N; j++) // Examining the possibility of connecting A[i]
            {
                if (A[i] > A[j]) // Here occurs a single decrease
                {
                    if (C[i] < B[j] + 1)
                    {
                        C[i] = B[j] + 1;
                        if (C[i] > V) V = C[i];
                    }
                }
                else // Here it can be connected without a decrease
                {
                    if (B[i] < B[j] + 1)
                    {
                        B[i] = B[j] + 1;
                        if (B[i] > V) V = B[i];
                    }
                    if (C[i] < C[j] + 1)
                    {
                        C[i] = C[j] + 1;
                        if (C[i] > V) V = C[i];
                    }
                }
            }
        }

        Console.WriteLine("Délka nejdelší vybrané podposloupnosti s nejvýše jedním poklesem: " + V);
    }
}
Leave a Comment