[LC] 300. Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [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.

Note:

There may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Time: O(N^2)

class Solution {

    public int lengthOfLIS(int[] nums) {

        if (nums == null || nums.length == 0) {

            return 0;

        }

        int[] arr = new int[nums.length];

        int res = 0;

        for (int i = 0; i < nums.length; i++) {

            arr[i] = 1;

            for (int j = 0; j < i; j++) {

                if (nums[j] < nums[i]) {

                    // note which one + 1

                    arr[i] = Math.max(arr[i], arr[j] + 1);

                }

            }

            res = Math.max(res, arr[i]);

        }

        return res;

    }

}

巴特西

[LC] 300. Longest Increasing Subsequence

最新文章

热门文章