300. Longest Increasing Subsequence

LeetCode

相比于《674. Longest Continuous Increasing Subsequence》，这题少了“连续”的条件，这意味着长度仅次于“以a[i]结尾的上升子序列”的子序列不再是以a[i - 1]结尾，而是以a[j], (0 <= j < i)结尾。

现在我们用文字重新解释长度仅次于f[i]的子序列：

  • 对于第674题来说，长度仅次于**“以a[i]结尾的连续上升子序列”**的子序列的结尾必定在i - 1，因为序列是连续的。
  • 对于本题来说，长度仅次于**“以a[i]结尾的上升子序列”**的子序列的结尾可能在[0, i)任意一处，因为序列不一定连续。

所以，对于所有的f[i]，我们都要考察以a[j] (for all 0 <= j < i)结尾的子序列f[j]可以达到的最大长度，达到最大长度的那个子序列就是子问题。

状态转移方程：

  • f[j] = max{ f[j] } (for all 0 <= j < i and a[j] < a[i])
  • f[i] = max{ f[j] + 1 }

初始条件：f[0] = 1

class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length() <= 1) {
            return nums.length();
        }
        int f[] = new int[nums.length()];
        f[0] = 1;
        int largest = f[0];
        // i and j traverse from left to right which means that 
        // they first calculate the first few terms of f[i] = f[j] + 1
        for (int i = 1; i < nums.length(); i++) {
            int maxFj = 0;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    maxFj = Math.max(maxFj, f[j]);
                }
            }
            f[i] = maxFj + 1;
            largest = Math.max(largest, f[i]);
        }
        return largest;
    }
}