300. Longest Increasing Subsequence

300. Longest Increasing Subsequence

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

문제

풀이

Example 1의 dp 테이블이다.
nums[i]를 왼쪽부터 시작하는 것이 아니라 맨 오른쪽에서 시작하는 것이다.
1. i = 7, nums[7] = 18일 때에는 처음 시작하는 것이므로 1을 저장한다.
2. i = 6, nums[6] = 101일 때에는 101>18이므로 넘어가고 그 이후에는 없으므로 1을 저장한다.
3. i = 5, nums[5] = 7일 때에는 7<101이므로 1 + dp[6] = 2이다. 또한 7 < 18이므로 1 + dp[7] = 2이다. 최대값은 2이므로 dp에 2를 저장한다.
4. i = 4, nums[4] = 3일 때 3<7이므로 1 + dp[5] = 3, 3<101이므로 1 + dp[6] = 2, 3<18이므로 1 + dp[7] = 2이다. 최대값은 3이므로 3을 저장한다.
이런식으로 dp값을 저장하고 dp값중 최대값인 4를 리턴해주면 된다.
이것을 코드로 나타내면 다음과 같다.

nums를 뒤에서 부터 시작하고 nums[i] > nums[j]라면 그냥 넘어가고 그렇지 않으면 최대값을 갱신하면 된다.

결과