您现在的位置是:首页 > 学习之路 > ACM||算法ACM||算法

动态规划 | 序列型动态规划 未完待更

卞振伟2019-03-01【ACM||算法】人已围观

简介这个专栏将有名的最长序列问题展开
单独划分专题
以发现普遍规律

76. 最长上升子序列

中文English

给定一个整数序列,找到最长上升子序列(LIS),返回LIS的长度。

Example

样例 1:
	输入:  [5,4,1,2,3]
	输出:  3
	
	解释:
	LIS 是 [1,2,3]


样例 2:
	输入: [4,2,4,5,3,7]
	输出:  4
	
	解释: 
	LIS 是 [2,4,5,7]

Challenge

要求时间复杂度为O(n^2) 或者 O(nlogn)

Clarification

最长上升子序列的定义:

最长上升子序列问题是在一个无序的给定序列中找到一个尽可能长的由低到高排列的子序列,这种子序列不一定是连续的或者唯一的。
https://en.wikipedia.org/wiki/Longest_increasing_subsequence
 

public class Solution {
    /**
     * @param nums: An integer array
     * @return: The length of LIS (longest increasing subsequence)
     */
    public int longestIncreasingSubsequence(int[] nums) {
        // write your code here
        int n = nums.length;
        if(n == 0)
            return 0;
        
        int[] dp = new int[n];
        int ans = 0;
        for(int i = 0; i < n; ++i){
            dp[i] = 1;
            for(int j = 0; j < i; ++j){
                if(dp[j]+1 > dp[i] && nums[j] < nums[i])
                    dp[i] = dp[j] + 1;
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}

Tags:

很赞哦! ()

文章评论

站点信息

  • 建站时间:2018-11-25
  • 网站程序:帝国CMS7.5
  • 文章统计:118篇文章
  • 标签管理标签云
  • 统计数据百度统计
  • 网站地图XML网站地图
  • 微信公众号:扫描二维码,关注我的公众号
  • GitHub:扫描二维码,关注我的GitHub

客服在线

QQ客服

客服微信扫码

服务时间

周一至周日 9:00-21:00