Longest Increasing Subsequence

🔗 문제 링크

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

🔍 문제 설명

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].

⚠️ 제한사항

• $1 <= nums.length <= 2500$

• $-10^4 <= nums[i] <= 10^4$

🗝 풀이 (언어 : Java)

모든 원소들은 1을 기본값으로 갖고 시작한다.(부분배열의 최소값은 1이므로) 두번째 원소부터 시작해서 앞의 원소들 모두와 비교해서 앞의 원소보다 크면 앞 원소의 부분 배열 길이 +1로 갱신해준다. 매번 이중에 최대값으로 갱신해준다. 다시 최대값을 찾기위해 반복문을 또 돌지않고 앞과정에서 변수로 최대값을 저장해서 반환한다.

import java.util.Arrays;

class Solution {
    public int lengthOfLIS(int[] nums) {
        int len = nums.length, answer = 1;
        int[] dp = new int[len];
        // 부분 배열 길이의 최소값은 1
        Arrays.fill(dp, 1);
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j])
                    dp[i] = Math.max(dp[i], dp[j]+1);
            }
            answer = Math.max(dp[i], answer);
        }
        return answer;
    }
}