[LeetCode] 300. Longest Increasing Subsequence

문제링크

배열이 주어졌을 때, 배열의 subset 중에서 배열의 원소들이 증가하는, 가장 긴 subset의 길이를 구하는 문제이다.

주어진 배열이 [10, 9, 2, 5, 3, 7, 101, 18] 일 때,

10	9	2	5	3	7	101	18

i=0일 때 [10]이 가능하므로 arr[0] = 1이다.

10	9	2	5	3	7	101	18
1

i=1일 때 9는 10보다 작으므로 [10] 혹은 [9]만 가능하다. 따라서 arr[1] = 1이다.

10	9	2	5	3	7	101	18
1	1

i=2일 때도 역시 1이다.

10	9	2	5	3	7	101	18
1	1	1

i=3일 때, 5는 2보다 크므로 [2,5]가 가능하다. 따라서 arr[3] = arr[2] + 1 = 2이다.

10	9	2	5	3	7	101	18
1	1	1	2

i=4일 때, 3은 2보다 크므로 arr[4] = arr[2] + 1 = 2이다.

10	9	2	5	3	7	101	18
1	1	1	2	2

i=5일 때, 7은 2, 5, 3보다 큰 데, 이 중 최댓값은 arr[3] = arr[3] = 2이므로 arr[5] = 2 + 1 =3이다.

10	9	2	5	3	7	101	18
1	1	1	2	2	3

i=6일 때, 101은 모든 숫자들보다 큰 데, 이 중 최댓값은 arr[5] = 3이므로, arr[6] = arr[5] + 1 = 4이다.

10	9	2	5	3	7	101	18
1	1	1	2	2	3	4

i=7일 때, 18은 101을 제외한 나머지 숫자들보다 큰 데, 이 중 최댓값은 3이므로 arr[7] = 3 + 1 = 4이다.

10	9	2	5	3	7	101	18
1	1	1	2	2	3	4	4

따라서 조건을 만족하는 가장 긴 subset의 길이는 배열의 최댓값인 4이다.

위의 과정을 정리하면

j < i 일 때, arr[i]의 값은 arr[j]<arr[i]인 j들 중에서 arr[j]의 최댓값에 1을 더한 값과 같다.
arr[i] = max(arr[j]) + 1 where 1 <= j <= i-1 and nums[j] < nums[i]

이를 코드로 작성하면 아래와 같다.

int arr[2501];

int lengthOfLIS(int* nums, int numsSize){
    for(int i=0;i<numsSize;i++)
    {
        if(i==0)
        {
            arr[i]=1;
            continue;
        }
        int max=0;
        for(int j=0;j<i;j++)
        {
            if(nums[j]>=nums[i]) continue;
            else
            {
                if(arr[j]>max) max=arr[j];
            }
        }
        arr[i]=max+1;
    }

    int max=0;
    for(int i=0;i<numsSize;i++)
    {
        if(arr[i]>max) max=arr[i];
    }

    return max;
}