LeetCord - 300.Longest Increasing Subsequence

순서.

이중포문을 사용한 해결.

이진탐색을 사용한 해결.

 

1. 주어진 배열의 길이만큼의 DP 배열을 생성하고, 모든 요소를 1로 초기화합니다.

2. 이중 포문을 사용하여 배열이 순차적으로 증가하는 부분 수열의 정보를 DP에 기록합니다.

• 내부 포문에서는 현재 요소(nums[i])와 이전 요소(nums[j])를 비교하여, 현재 요소가 더 큰 경우에만 DP 값을 갱신합니다. dp[i] 값은 dp[j] + 1과 비교하여 더 큰 값을 선택합니다.

모든 요소에 대해 반복하면서 최대 부분 수열의 길이를 업데이트해나갑니다. 

 

public class Solution {
    public int LengthOfLIS(int[] nums) {
        int[] dp = new int[nums.Length];
        int answer = 1;
        
        for (int i = 0; i < nums.Length; i++)
        {
            dp[i] = 1;
        }

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

 

 

이진 탐색

이진 탐색을 사용해 순차적으로 증가하는 부분 수열을 담는 list를 업데이트 시켜줍니다.

• 리스트의 마지막 숫자가 현재 순회 중인 배열의 숫자보다 작다면, 이진 탐색을 사용하여 리스트에 적절한 위치에 숫자를 삽입합니다. 이를 통해 리스트에는 순차적으로 증가하는 부분 수열이 담기게 됩니다.

public class Solution {
    public int LengthOfLIS(int[] nums) {
         int Binary_Search(List<int> array, int target)
         {
            int left = 0;
            int right = array.Count - 1;

            while (left < right)
            {
                int mid = left + (right - left) / 2;

                if (array[mid] == target)
                {
                    return mid;
                }
                else if (array[mid] < target)
                {
                    left = mid + 1;
                }
                else
                {
                    right = mid;
                }
            }
            return left;
        }

        List<int> list = new List<int>() { nums[0] };

        for (int i = 0; i < nums.Length; i++)
        {
            if (list[list.Count-1] < nums[i])
            {
                list.Add(nums[i]);
            }
            else
            {
                int idx = Binary_Search(list, nums[i]);
                list[idx] = nums[i];
            }
        }
        return list.Count;
    }
}