C# - Longest Increasing Subsequence

📘 300. Longest Increasing Subsequence

🔹 문제 설명

정수 배열 nums가 주어질 때,

배열에서 오름차순으로 증가하는 가장 긴 부분 수열의 길이를 구하라.

• 부분 수열(subsequence):(연속된 값일 필요는 없음)
• 원래 배열에서 순서를 유지하면서 일부 원소를 건너뛰어 선택할 수 있음

---

🔸 예시

Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4

설명: 가장 긴 오름차순 부분 수열은 [2, 3, 7, 101] 이므로 길이는 

---

🔹 조건

• 1 <= nums.length <= 2500
• 10⁴ <= nums[i] <= 10⁴

---

🎯 목표

👉 배열에서 가장 길게 오름차순으로 증가하는 부분 수열을 찾아서

그 길이를 반환하는 함수를 작성하는 것이 목표야.

---

✅ 예시 2

Input: nums = [0, 1, 0, 3, 2, 3]
Output: 4
설명: [0, 1, 2, 3] 이 가장 길다

---

🧠 핵심 개념

이 문제는 전형적인 동적 계획법 (DP) 또는 이진 탐색을 이용한 최적화 문제야.

• 기본 DP 풀이: O(n²)
• 이진 탐색 최적화: O(n log n)

using System;

public class Program
{
    public static void Main()
    {
        int[] nums = new int[] { 10, 9, 2, 5, 3, 7, 101, 18 };

        Console.WriteLine("Input Array: " + string.Join(", ", nums));

        int result = FindLengthOfLIS(nums);

        Console.WriteLine("Longest Increasing Subsequence Length: " + result);
    }

    public static int FindLengthOfLIS(int[] nums)
    {
        int n = nums.Length;
        if (n == 0) return 0;

        int[] dp = new int[n];
        for (int i = 0; i < n; i++)
            dp[i] = 1;  // 최소 자기 자신

        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (nums[j] < nums[i])
                {
                    dp[i] = Math.Max(dp[i], dp[j] + 1);
                }
            }
        }

        int maxLength = 0;
        for (int i = 0; i < n; i++)
            maxLength = Math.Max(maxLength, dp[i]);

        return maxLength;
    }
}