[LeetCode] 300. Longest Increasing Subsequence

LeetCode - Problems - Algorithms - 300. Longest Increasing Subsequence

Problem Description

Given an integer array nums, return the length of the longest strictly increasing subsequence.

 

Example:

 

Constraints:

My Solution (C#)

public int LengthOfLIS(int[] nums)
{
    int numsLength = nums.Length;
    int[] maxSubsequenceLengths = new int[numsLength];
    Array.Fill(maxSubsequenceLengths, 1);   //maxSubsequenceLengths[i]는 0부터 [i]까지를 비교했을 때 최장 수열 길이.

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

 

동적 프로그래밍으로 진행해야했다.

더 빠르게 진행할 수 있는 풀이가 있는 것 같은데 이 부분은 나중에 진행해봐야겠다.

유튜브 해설을 봐도 이해가 애매해서.. 어찌저찌 풀긴 했는데, 이게 동적프로그래밍 자체에 대한 이해도를 높히는 건 아니었다.

조금 더 쉬운 난이도로 동적 프로그래밍을 이해하고 적용할 수 있는 문제를 몇가지 더 풀어봐야겠다...