Longest alternating subsequence in c#

Programming C#
1

The Longest Alternating Subsequence (LAS) problem involves finding the longest subsequence of a sequence such that the elements in the subsequence are in alternating order. Specifically, this means that the subsequence must alternate between increasing and decreasing values.

Algorithm Explanation

  1. Dynamic Programming Table: Use two arrays to keep track of the longest subsequence lengths:

    • up[i]: The length of the longest alternating subsequence that ends with the i-th element and is currently increasing.
    • down[i]: The length of the longest alternating subsequence that ends with the i-th element and is currently decreasing.

  2. Initialization: Both arrays are initialized to 1 because every single element is an alternating subsequence of length 1.

  3. Filling the Arrays: Iterate through the array:

    • For each pair of indices (i, j) where j < i, check:
      • If arr[i] > arr[j], then up[i] can be updated to down[j] + 1 (meaning that arr[j] was decreasing before arr[i]).
      • If arr[i] < arr[j], then down[i] can be updated to up[j] + 1 (meaning that arr[j] was increasing before arr[i]).

  4. Compute Result: The longest alternating subsequence will be the maximum value found in either up or down.

C# Implementation

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

using System;

class Program
{
    static void Main()
    {
        int[] arr = { 1, 5, 4, 3, 2, 8, 6, 7 };
        int result = LongestAlternatingSubsequence(arr);
        Console.WriteLine("Length of Longest Alternating Subsequence: " + result);
    }

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

        // Arrays to store the lengths of the longest subsequence
        int[] up = new int[n];
        int[] down = new int[n];

        // Initialize the arrays
        for (int i = 0; i < n; i++)
        {
            up[i] = 1;    // Minimum length is 1
            down[i] = 1;  // Minimum length is 1
        }

        // Fill the up and down arrays
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (arr[i] > arr[j])
                {
                    up[i] = Math.Max(up[i], down[j] + 1);
                }
                else if (arr[i] < arr[j])
                {
                    down[i] = Math.Max(down[i], up[j] + 1);
                }
            }
        }

        // The result is the maximum value in both up and down arrays
        int maxLength = Math.Max(up[n - 1], down[n - 1]);
        for (int i = 0; i < n; i++)
        {
            maxLength = Math.Max(maxLength, Math.Max(up[i], down[i]));
        }

        return maxLength;
    }
}

Explanation of Code

  1. Input: An array arr is defined with integer values.
  2. LongestAlternatingSubsequence Function:
    • Initialization: Two arrays up and down are initialized to store the lengths of the longest subsequences ending at each index, starting with a value of 1.
  3. Filling the Arrays:
    • A nested loop iterates through the array. For each element arr[i], it checks all previous elements arr[j].
    • If arr[i] is greater than arr[j], it updates up[i] based on the value of down[j] + 1.
    • If arr[i] is less than arr[j], it updates down[i] based on the value of up[j] + 1.
  4. Computing Result: Finally, it computes the maximum length by checking the last values of both arrays and iterating through the arrays to ensure all maximum values are considered.

Complexity

  • Time Complexity: O(n^2), where n is the length of the array. This is due to the nested loops for filling the up and down arrays.
  • Space Complexity: O(n), for the storage of the up and down arrays.

This approach provides a clear and systematic way to find the longest alternating subsequence while ensuring the code remains efficient and maintainable.