Longest Increasing Subsequence

https://leetcode.com/problems/longest-increasing-subsequence/description/

Given a sequence of integers, find the longest increasing subsequence (LIS).

You code should return the length of the LIS.

Thoughts

看到数组求某性质的值想DP。如果让f[i][j]表示以从i到j的substring最长升序则无法知道当前nums[i]是否能和已有子序列拼接。所以必须要存下能与当前nums[i]作比较的最后元素。因此想到f[i]为以nums[i]为尾组成的序列的LIS。

https://www.zhihu.com/question/23995189

给定一个数列，长度为N，

设F_{k}为：以数列中第k项结尾的最长递增子序列的长度.

求F_{1}..F_{N} 中的最大值.

设A为题中数列，状态转移方程为：

（根据状态定义导出边界情况）

Code

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        int max = 0;
        for (int i = 0; i < n; i++) {
            f[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    f[i] = Math.max(f[i], f[j] + 1);
                }
            }
            max = Math.max(max, f[i]);
        }

        return max;
    }
}

Analysis

做题耗时21min。

Errors:

1. 结果直接返回了f[n-1].

TC: O(n^2).

此题还有O(nlgn)解法, 参见二分法章节。