(LeetCode) 300. Longest Increasing Subsequence

300. Longest Increasing Subsequence

• Explore : Interview > Top Interveiw Questions > Medium Collection
• 분류 : Dynamic Programming
• 난이도 : Medium

Problem

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

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Example 1

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2

Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3

Input: nums = [7,7,7,7,7,7,7]
Output: 1

Constraints

• 1 <= nums.length <= 2500
• -10^4 <= nums[i] <= 10^4

Solution

Exapnder

class Solution {
    fun lengthOfLIS(nums: IntArray): Int {
        var dp = IntArray(nums.size){ 1 }

        for (i in 1 until nums.size) {
            for (j in 0 until i) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1)
                }
            }
        }
        return dp.max()!!
    }
}

Point of Thinking

• 주어진 nums만큼, index가 원소의 index을 의미하고, 값은 증가한 만큼의 부분 수열의 길이인 dp 배열을 생성한다.
• dp 배열 전체에 대해 LIS의 최소 값인 1로 초기값을 부여한다.
• 현재 계산하려는 목표 금액이 i원이라면 dp[i]의 값과 주어진 코인들을 하나씩 빼가면서 카운트를 올려준다.
• 앞에 있는 원소보다, 뒤에있는 원소가 더 크면 값을 계속해서 갱신해 나가서 순회 후 최대값을 출력하면 Accpeted.
• maxOrNull()을 leetcode가 인지하지 못하고 아래와 같은 에러메시지를 뱉는다.
  • error: unresolved reference: maxOrNull return dp.maxOrNull()!! ^
• deprecated된 max()를 !!로 써서 호출해줬다. 사실 순회하면서 값을 비교해나가면 시간복잡도상 이득을 볼 수 있지만 leetcode 풀이의 목적이 코틀린 숙련도 상승이므로 max()를 사용하였다.