(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

1
2
3
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

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

Example 3

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

Constraints

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

Solution

Exapnder
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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()를 사용하였다.