C# Coding Test Course, Finding the Longest Increasing Subsequence

Problem Description

Let’s solve the problem of finding the length of the longest increasing subsequence in a given array. An increasing subsequence is a subarray of elements from the array that have different indices and are sorted in ascending order. For example, for the array [10, 22, 9, 33, 21, 50, 41, 60, 80], the longest increasing subsequence is [10, 22, 33, 50, 60, 80], which has a length of 6.

Problem Definition

Write a method that returns the length of the longest increasing subsequence in a given integer array arr.

Input

• The first line contains the length of the array n. (1 ≤ n ≤ 1000)
• The second line contains n integers. Each integer is -10^6 ≤ arr[i] ≤ 10^6.

Output

Print the length of the longest increasing subsequence.

Example

Input

9
10 22 9 33 21 50 41 60 80

Output

6

Solution Method

Among the various algorithms for finding the longest increasing subsequence, the most commonly used method is Dynamic Programming. This approach breaks the problem into smaller subproblems, solving each one and using the results to solve the overall problem.

Step-by-Step Explanation

1. Initialization of Array: Assume the length of the given array arr is n. We initialize a dynamic programming array dp to store the length of the longest increasing subsequence up to each index i. Initially, we set the value to 1 for each element, as each element can form a subsequence by itself.
2. Nested Loops: Use nested loops to compare all pairs of indices i and j. Here, i should be greater than j, and if arr[i] is greater than arr[j] (i.e., satisfying the increasing condition), we update the value of dp[i]. Specifically, we set dp[i] = max(dp[i], dp[j] + 1). This means adding 1 to the length of the sequence that includes j.
3. Finding the Maximum Length: After calculating all sequence lengths, we find the maximum value in the dp array and return it.

C# Implementation

using System;

class Program
{
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        int[] arr = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);

        int[] dp = new int[n];
        for (int i = 0; i < n; i++)
        {
            dp[i] = 1; // Each element can form at least 1 subsequence
        }

        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (arr[i] > arr[j] && dp[i] < dp[j] + 1)
                {
                    dp[i] = dp[j] + 1;
                }
            }
        }

        int maxLength = dp[0];
        for (int i = 1; i < n; i++)
        {
            if (dp[i] > maxLength)
            {
                maxLength = dp[i];
            }
        }

        Console.WriteLine(maxLength);
    }
}

Time Complexity

The time complexity of this algorithm is O(n^2). This is because it uses two nested loops. Both the outer and inner loops run for each length of the array, leading to a total of n * n operations in the worst case. The space complexity is O(n), which is the space needed to store the dp array.

Conclusion

In this tutorial, we implemented an algorithm to find the longest increasing subsequence in C#. This problem is frequently encountered in coding tests and is very useful for learning and mastering the basics of dynamic programming. Through consistent practice, one can develop the thinking and approaches needed to solve a variety of problems.