How to Find the Length of the Longest Increasing Subsequence usi

  • 时间:2020-09-18 17:01:02
  • 分类:网络文摘
  • 阅读:90 次

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(n^2) complexity.
Follow up: Could you improve it to O(nlogn) time complexity?

Length of the Longest Increasing Subsequence using DP Algorithm

Surely, we can bruteforce, but that will take O(2^n) complexity i.e. each number has two choices: take or not take. This is not ideal. We could use f[i] to represent the longest length subsequence that ending at element nums[i]. Thus, we can reduce the runtime complexity to O(N^2) by checking each pair of (nums[j], nums[i]) and update f[i] = max(f[i], f[j] + 1) if nums[j] is smaller than nums[i].

The Longest Increasing Subsequence (LIS) can be computed via the following Dynamic Programming Algorithm i.e. C++.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.empty()) return 0;
        vector<int> f(nums.size(), 1);
        int ans = 1;
        for (int i = 1; i < nums.size(); ++ i) {
            for (int j = 0; j < i; ++ j) {
                if (nums[j] < nums[i]) {
                    f[i] = max(f[i], f[j] + 1);
                    ans = max(ans, f[i]);
                }
            }
        }
        return ans;
    }
};
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.empty()) return 0;
        vector<int> f(nums.size(), 1);
        int ans = 1;
        for (int i = 1; i < nums.size(); ++ i) {
            for (int j = 0; j < i; ++ j) {
                if (nums[j] < nums[i]) {
                    f[i] = max(f[i], f[j] + 1);
                    ans = max(ans, f[i]);
                }
            }
        }
        return ans;
    }
};

Then, we need to find out the maximum value in f[0] to f.back(). The space requirement is O(N).

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
不同包装的牛奶,你知道该如何选择吗  冬天吃羊肉如何去掉羊膻味及饮食禁忌  适度喝啤酒预防骨质疏松保持关节弹性  关于鸡蛋营养及其食用方法的十大误区  腊肉的风味和特点及腊肉的制作全过程  腊肉的营养价值及腊肉的食用禁忌  煲汤的诀窍及胡萝卜熟吃煮汤更营养  胡萝卜不但可以保护视力还对精子有益  节令食品年糕的营养价值与食用禁忌  如何吃辣椒不上火?怎样吃辣椒更健康? 
评论列表
添加评论