題目

他說他會給我們一個整數陣列，然後我們要找出最長的遞增長度，並回傳。

Example 1:
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
因為可以找到他的最長遞增子序列為[2,3,7,101],也可以是[2,5,7,18]......不只一組的遞增子序列，然後他們的長度剛好也都是一樣最長的。所以Output就是4。

想法

我讓這題的dp[i]代表的就是每個位置可以往前沿出去找到最長遞增子序列的長度，就是這個遞增子序列是以第i個數字為結尾的，然後因為每個數字自己都能當這個子序列，所以dp初始值=1，然後我想到的是用兩個for迴圈來做判斷，外層做的事情是跑現在要算的數；內層的是在i前面的所有元素。如果 nums[j] < nums[i]，就代表我可以接在j後面，所以可以更新max()來比較dp[i]和dp[j] + 1誰大，這樣一直跑跑跑到最後就是我們要找的「最長遞增子序列長度」了!

程式碼

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1); // 每個元素可以自己當一個子序列

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) { // 判斷可不可以接
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        int ans = 0;
        for (int i = 0; i < dp.length; i++) {
        ans = Math.max(ans, dp[i]);   //找dp[]裡最大的那個數
        }
        return ans;
    }
}

執行成功!

剩十篇了。。。