300. Longest Increasing Subsequence

2016-07-06 01:46:00

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

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that 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?

解答：

public class Solution {
//State: f[i] is from 0 - i the longest length of increasing subsequence
//Function: f[i] = Max(f[i - k] + 1) if nums[i] > nums[k]
//Initialize: f[i] = 1;
//Result: f[nums.length - 1];
public int lengthOfLIS(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}

    int[] f = new int[nums.length];
    Arrays.fill(f, 1);
    int max = 1;
    for (int i = 1; i  nums[k]) {
                f[i] = Math.max(f[i], f[k] + 1);
            }
        }
        max = Math.max(max, f[i]);
    }

    return max;
}

}

关键字：leetcode, 算法, nums, length

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符，请点击举报进行投诉反馈！