300. Longest Increasing Subsequence - Medium

前往題目

想法

• 毫無頭緒因為不需要連續，中間可以斷掉…

思路

有很多種作法:

• DFS
• DFS with cache
• DP

採用DP，因為$O(n^2)$，相較於DFS $O(2^n)$

1. 觀察規律，從後往前，因為最後一個一定是只有自己，也就是長度為1，以此往前推

影片中解釋得更清楚

Code

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] lis = new int[nums.length];
        Arrays.fill(lis, 1);

        // Go from last index to the first
        for (int i = nums.length - 1; i >= 0; --i) {
            // Check the following subsequence
            for (int j = i + 1; j < nums.length; ++j) {
                // Make sure increasing
                if (nums[i] < nums[j]) {
                    lis[i] = Math.max(lis[i], 1 + lis[j]);
                }
            }
        }

        int res = Integer.MIN_VALUE;

        for (int num : lis) {
            if (res < num) res = num;
        }

        return res;
    }
}

2024/04/25

• 忘得一乾二淨，不過解法還是蠻好理解的