[Leetcode] 300. Longest Increasing Subsequence

Identifying the Problem

주어진 수열에서 가장 긴 오름차순 부분 배열의 크기를 구한다.

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: 가장 긴 부분 배열의 길이는 [2,3,7,101] 이므로 길이는 4이다.

Organizing thoughts

핵심 IDEA는 수열을 탐색하면서 해당 index에서 가능한 가장 큰 배열에 길이를 따로 저장해 두는 것이다.

즉 이전 수들 중에서 다음 수로 증가했을 때, 이전 수들 중에서 가능한 가장 큰 배열 길이 + 1을 하는 것이다. 

초기 첫번째는 count가 무조건 1이 된다.

nums = [10,9,2,5,3,7,101,18] 이라면

count = [1,1,1,2,2,3,4,3] 이 되고, 여기서 가장 큰 max 값만 따로 정답으로 내면 된다.

 

더 깊게 설명하자면,

5를 탐색할 때 5 이전 5보다 작은 값은 [2]이고, 2의 count값 + 1 한 것이 count[3] 이 된다.

7을 탐색할 때 7 이전 7보다 작은 값은 [2,5,3]이고

각각의 count값은 [1,2,2] 가 되고, count 값의 최고 값 2 + 1 한 것이 count[5] 가 된다.  

Sourcecode

int find_max(int* c, int n) //수열에서 가장 큰 값을 찾는 함수
{
    int max = 0;
    for(int i = 0; i<n ; i++)
    {
        max = max<= c[i] ?  c[i] : max;
    }
    
    return max;
}

int f_max(int a, int b) //max 함수
{
    if (a>b) return a;
    else return b;
}

int lengthOfLIS(int* nums, int numsSize)
{
    if(numsSize < 2) return numsSize; //nums 길이가 0,1인 경우 답은 0,1이다.
    
    int* count = malloc(sizeof(int) * (numsSize)); //count 배열 생성

    count[0] = 1; //count[0]은 무조건 1이다.
    int max = 1; //비교용 max 
    			//count[0]이 1이므로 초기값은 1로 시작
    
    for(int i = 1; i< numsSize; i++)
    {
        count[i] = 1; //이전에서 다음으로 증가하지 않는 경우도 있기에 
        			  //count의 모든 초기값은 1로 대입
        
        for(int k = 0; k<i ; k++)
        {
            if(nums[i] > nums[k])  //수가 증가했다면 가능한 max의 값을 찾는다.
            {   
            	max = f_max(max,count[k]); 
                count[i] = max+1;
            }
        }
        max = 1; //i가 넘어가므로 max를 초기화 시켜준다.
    }

    return find_max(count, numsSize);
}

Mistake

• max를 초기화시키는 과정을 생략했다.