[Dynamic Programming][Medium] 300. Longest Increasing Subsequence

https://leetcode.com/problems/longest-increasing-subsequence/description

 

Q. 주어진 정수 배열 nums에서 증가하는 sub sequence의 가장 긴 길이를 찾아라. 

 

 

Solution

 특정 조건을 만족하는 단계수를 찾아야 하므로, 전 값보다 지금이 크면 1 증가 시킨다. 

 배열 끝까지 가면 멈춘다. 

 현재 수가 조건을 만족해도, 다음 작은 수가 만족하고 또 더 작을 수 있으므로, 이후로 자체 loop를 다 돌아야 한다. 

 약간 backtrack 스럽기도 하다. 

 

 논리대로 코드를 만든다. 

 

 

int length_help(vector<int>& vCache, vector<int>& nums, int idx, int last)
{
    if(idx >= nums.size())  return 0;

    if(vCache[idx] >= 0)    return vCache[idx];

    int maxLen = 0;
    for(int q = idx; q < nums.size(); ++q)
    {
        if(nums[q] > last)
            maxLen = max(maxLen, 1 + length_help(vCache, nums, q+1, nums[q]));
    }
    return vCache[idx] = maxLen;
}

int lengthOfLIS(vector<int>& nums) 
{
    vector<int> vCache;
    vCache.resize(nums.size(), -1);
    return length_help(vCache, nums, 0, INT_MIN);
}

 

풀리긴 했지만, 속도가 50% 이하로, 

일반적인 해법이 아니다. 

 

추후 다시 돌아와 최적해를 구해본다.