Longest Increasing Subsequence (LIS)

Problem definition

• 주어진 배열 값들 중에서 증가순으로 이루어진 가장 긴 subsequence의 길이를 구하는 문제
• 대표적인 DP 문제로 응용 범위가 넓다.

arr[] = {10, 22, 9, 33, 21, 50, 41, 60, 80} Output: 6 (Length of {10, 22, 33, 50, 60, 80})

Optimal Substructure

• L(i)는 arr[0..n-1]가 주어질 때 arr[0..i]까지의 LIS의 길이이다. 단 arr[i]가 LIS의 마지막 원소로 포함 된다.

L(i) = { 1 + Max(L(j)) } where j < i and arr[j] < arr[i] and if there is no such j then L(i) = 1

• i 이전까지의 모든 subsequence에 대해 i가 포함될 경우와 포함 안될 경우를 고려한다.
• subsequence의 마지막 원소보다 arr[i]가 크면 MAX값에 + 1 (i가 포함될 경우에 해당), 크지 않으면 기존 MAX값 사용 (i가 포함 안될 경우에 해당)

Code - Recursive solution (Top-down manner)

• 참고로 이 문제는 곧장 Bottom-up manner로 가는게 좋다. (Recursive solution은 이해하기 어려움)

// max_ref는 output중 하나로 진짜 최대값을 의미한다. (LEND)
int _lis(int arr[], int n, int *max_ref) 
{
    /* Base case */
    if(n == 1)
        return 1;
  
    int res, max_ending_here = 1; // length of LIS ending with arr[n-1]
  
    /* Recursively get all LIS ending with arr[0], arr[1] ... arr[n-2].
       If arr[i-1] is smaller than arr[n-1], and max ending with 
       arr[n-1] needs to be updated, then update it */
    for (int i = 1; i < n; i++)
    {
        res = _lis(arr, i, max_ref);
        // 마지막 것이 포함될 경우 기존 LEND값을 갱신한다.
        if (arr[i-1] < arr[n-1] && res + 1 > max_ending_here)
            max_ending_here = res + 1;
    }
  
    // Compare max_ending_here with the overall max. And update the
    // overall max if needed (LEND이 크면 LMAX는  LEND값을 취한다)
    if (*max_ref < max_ending_here)
       *max_ref = max_ending_here;
  
    // Return length of LIS ending with arr[n-1]
    return max_ending_here; // max_ending_here는 output 중 하나로
                            // 마지막 것이 포함된 최대값을 의미한다. (LEND)
}
 
// The wrapper function for _lis()
int lis(int arr[], int n)
{
    // The max variable holds the result
    int max = 1;
  
    // The function _lis() stores its result in max
    _lis( arr, n, &max );
  
    // returns max
    return max;
}
 
/* Driver program to test above function */
int main(int argc, char** argv)
{
    int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("Length of LIS is %d\n",  lis( arr, n ));
 
    return 0;
}

• Time complexity: O(2ⁿ)

Top-down 방식을 tree로 이해하기

Code - Dynamic Programming solution (Bottom-up manner)

/* lis() returns the length of the longest increasing subsequence
   in arr[] of size n */
int lis( int arr[], int n )
{
   int *lis, i, j, max = 0;
   lis = (int*) malloc(sizeof( int ) * n);
  
   /* Initialize LIS values for all indexes */
   for ( i = 0; i < n; i++ )
      lis[i] = 1;
     
   /* Compute optimized LIS values in bottom up manner */
   for ( i = 1; i < n; i++ )
      for ( j = 0; j < i; j++ )
         if ( arr[i] > arr[j] && lis[i] < lis[j] + 1)
            lis[i] = lis[j] + 1;
     
   /* Pick maximum of all LIS values */
   for ( i = 0; i < n; i++ )
      if ( max < lis[i] )
         max = lis[i];
  
   /* Free memory to avoid memory leak */
   free( lis );
  
   return max;
}
 
/* Driver program to test above function */
int main(int argc, char** argv)
{
    int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("Length of LIS is %d\n",  lis( arr, n ));
 
    return 0;
}

• Time complexity: O(n²)
• 참고로 LIS를 O(N logN)에 푸는 방법이 있다. 

Bottom-up 방식을 table로 이해하기