LintCode 76. Longest Increasing Subsequence 原创Java参考解答

LintCode 76. Longest Increasing Subsequence 原创Java参考解答

问题描述

http://www.lintcode.com/en/problem/longest-increasing-subsequence/

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

You code should return the length of the LIS.

Clarification

What’s the definition of longest increasing subsequence?

  • The longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence’s elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique.
  • https://en.wikipedia.org/wiki/Longest_increasing_subsequence

Example

For [5, 4, 1, 2, 3], the LIS is [1, 2, 3], return 3
For [4, 2, 4, 5, 3, 7], the LIS is [2, 4, 5, 7], return 4

解题思路

  1. 找极值的问题,不难判断旨在题目考察动态规划。
  2. 定义本题的动态规划状态转移方程f[i]:到第i位置时发现的最长LIS长度。
  3. 状态初始化,每一个f[i]为1。
  4. 通过一个二重循环,依次计算i前面所有位置到第i位置的LIS长度。
  5. 最后循环整个数组,看哪一个位置有最长LIS长度。

参考代码

public class Solution { 
    /** 
     * @param nums: The integer array 
     * @return: The length of LIS (longest increasing subsequence) 
     */ 
    public int longestIncreasingSubsequence(int[] nums) { 
        // write your code here 
        if (nums == null || nums.length == 0) { 
            return 0;     
        } 
         
        // the longest subsequence length to the index(x) position 
        int[] f = new int[nums.length]; 
         
        for (int i = 0; i < nums.length; i++) { 
            f[i] = 1; 
        } 
         
        for (int i = 0; i < nums.length; i++) { 
            for (int j = 0; j < i; j++) { 
                if (nums[j] < nums[i]) { 
                    f[i] = Math.max(f[i], f[j] + 1); 
                } 
            } 
        } 
         
        int max = 0; 
        for (int i = 0; i < nums.length; i++) { 
            max = Math.max(f[i], max); 
        } 
 
        return max; 
    } 
} 

相关题目

LintCode All in One 原创题目讲解汇总

发表回复

您的电子邮箱地址不会被公开。