Longest Increasing Subsequence in c#

General
1

The Longest Increasing Subsequence (LIS) problem involves finding the longest subsequence in a sequence of numbers such that all elements in the subsequence are in increasing order. The subsequence does not need to be contiguous, meaning that elements can be taken from anywhere in the array as long as they maintain their relative order.

Algorithm Explanation

The most common approach to solve this problem uses dynamic programming:

  1. Dynamic Programming Array: Create a DP array dp where dp[i] will store the length of the longest increasing subsequence that ends with the element at index i.

  2. Initialization: Initialize each element of dp to 1 since the smallest increasing subsequence containing any element is the element itself.

  3. Fill the DP Array:

    • Loop through each element in the array.
    • For each element arr[i], check all previous elements arr[j] (where j < i).
    • If arr[i] > arr[j], it means arr[i] can extend the increasing subsequence ending at arr[j], so update dp[i] as follows: dp[i] = Math.Max(dp[i], dp[j] + 1).

  4. Compute Result: The length of the longest increasing subsequence will be the maximum value in the dp array.

C# Implementation

Here’s a sample implementation of the Longest Increasing Subsequence problem:

using System;

class Program
{
    static void Main()
    {
        int[] arr = { 10, 22, 9, 33, 21, 50, 41, 60, 80 };
        int result = LongestIncreasingSubsequence(arr);
        Console.WriteLine("Length of Longest Increasing Subsequence: " + result);
    }

    static int LongestIncreasingSubsequence(int[] arr)
    {
        int n = arr.Length;
        if (n == 0) return 0;

        int[] dp = new int[n];
        Array.Fill(dp, 1); // Initialize all lengths to 1

        // Fill the DP array
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (arr[i] > arr[j])
                {
                    dp[i] = Math.Max(dp[i], dp[j] + 1);
                }
            }
        }

        // Find the maximum length
        int maxLength = 0;
        for (int i = 0; i < n; i++)
        {
            maxLength = Math.Max(maxLength, dp[i]);
        }

        return maxLength; // Return the length of the longest increasing subsequence
    }
}

Explanation of Code

  1. Input: The program defines an array arr containing integers for which we want to find the longest increasing subsequence.
  2. LongestIncreasingSubsequence Function:
    • Initialization: It first initializes an integer array dp of the same length as arr, with all values set to 1. This represents that the smallest increasing subsequence length for any individual element is 1.
  3. Filling the DP Array:
    • Two nested loops iterate through the array. The outer loop iterates through each element arr[i], while the inner loop checks all previous elements arr[j].
    • If arr[i] is greater than arr[j], it updates dp[i] to store the maximum length of increasing subsequences that can end with arr[i].
  4. Compute Result: After filling the dp array, it calculates the maximum value from dp, which gives the length of the longest increasing subsequence.
  5. Return Result: The function returns the maximum length.

Complexity

  • Time Complexity: O(n²), where n is the length of the input array. This is due to the nested loops used to fill the dp array.
  • Space Complexity: O(n) for the dp array.

Optimization

While the above approach is straightforward, it can be optimized to O(n log n) using a method involving binary search combined with an auxiliary array to store the smallest tail values of increasing subsequences found so far. However, the O(n²) approach is simpler and often sufficient for moderate input sizes.