Cách tìm độ dài dãy con tăng liên tục dài nhất từ mảng số trong C#

Phương pháp LongestIncreasingSubsequence trả về độ dài dãy con tăng liên tục. Dùng vòng lặp for duyệt mảng, theo dõi số lượng phần tử tăng liên tiếp. Kết quả lưu giá trị max. Độ phức tạp O(N) vì mỗi phần tử duyệt một lần, không gian O(1) không dùng bộ nhớ thêm.

Độ phức tạp thời gian: O(N)

Độ phức tạp không gian: O(1)

Ví dụ: {2, 4, 6, 5, 8} → Output: 3 (dãy 2,4,6)

Ví dụ

public class Arrays
{
    public int LongestIncreasingSubsequence(int[] nums)
    {
        if (nums == null || nums.Length == 0)
        {
            return -1;
        }
        int res = 0, count = 0;
        for (int i = 0; i < nums.Length; i++)
        {
            if (i == 0 || nums[i] > nums[i - 1])
            {
                count++;
                res = Math.Max(res, count);
            }
            else
            {
                count = 1;
            }
        }
        return res;
    }
}

static void Main(string[] args)
{
    int[] nums = { 1, 3, 5, 4, 7 };
    Arrays s = new Arrays();
    Console.WriteLine(s.LongestIncreasingSubsequence(nums)); // Output: 3
}

Kết quả đầu ra

3

Lưu ý: Tên phương thức gốc có lỗi chính tả "Increaing" → đã sửa thành "Increasing". Code gốc dùng nums.Count() (cần using System.Linq) thay vì nums.Length.