首页 > 试题广场 > 最长递增子序列
[编程题]最长递增子序列
  • 热度指数:11776 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

对于一个数字序列,请设计一个复杂度为O(nlogn)的算法,返回该序列的最长上升子序列的长度,这里的子序列定义为这样一个序列U1,U2...,其中Ui < Ui+1,且A[Ui] < A[Ui+1]。

给定一个数字序列A及序列的长度n,请返回最长上升子序列的长度。

测试样例:
[2,1,4,3,1,5,6],7
返回:4
LIS问题,O(N 2 )解法就不说了,下面说下O(NlogN)的解法:
假设存在一个序列A[0..8] = 2 1 5 3 6 4 8 9 7,可以看出来它的LIS长度为5。
下面一步一步试着找出它。
我们定义一个序列B,然后令 i = 0 到 8 逐个考察这个序列。
此外,我们用一个变量end来记录B中最后一个数的下标。

首先,令B[0] = A[0] = 2,就是说当只有1一个数字2的时候,长度为1的LIS的最小末尾是2,这时end=0。

然后,把A[2]有序地放到B里,令B[0] = 1,就是说长度为1的LIS的最小末尾是1,B[0]=2已经被淘汰了,这时 end =1。

接着,A[2] = 5,A[2]>B[0],所以令B[1]=A[2]=5,就是说长度为2的LIS的最小末尾是5,很容易理解吧。这时候B[0..1] = 1, 5, end =1。

再来,A[3] = 3,它正好加在1,5之间,放在1的位置显然不合适,因为1小于3,长度为1的LIS最小末尾应该是1,这样很容易推知,长度为2的LIS最小末尾是3,于是可以把5淘汰掉,这时候B[0..1] = 1, 3, end = 2。

继续,A[4] = 6,比B中最大的数3还要大 ,于是很容易可以推知B[2] = 6, 这时B[0..2] = 1, 3, 6, end = 2。

A[5] = 4,它在3和6之间,于是我们就要把6替换掉,得到B[2] = 4,B[0..2] = 1, 3, 4, end 继续等于2。

A[6] = 8,它很大,比4大。于是继续往B中追加,B[3] = 8, end 变成3了。

A[7] = 9,得到B[4] = 9,此时B是1,3,4,8,9,end是4。

最后一个, A[8] = 7,它在4和8之间,所以我们知道,最新的B[3] =7,B[0..4] = 1, 3, 4, 7, 9, end = 4。

于是我们知道了LIS的长度为 end+1 = 5

注意: 这个1,3,4,7,9不是LIS字符串,比如本题例的LIS应该是1,3,4,8,9,7代表的意思是存储4位长度LIS的最小末尾是7, 所以我们的B数组,是存储对应长度LIS的最小末尾。有了这个末尾,我们就可以一个一个地插入数据。虽然最后一个A[8] = 7更新进去对于这组数据没有什么意义,但是如果后面再出现两个数字 8 和 9,那么就可以把8更新到B[4], 9更新到B[5],得出LIS的长度为6。

然后应该发现一件事情了:在B中插入数据是有序的,而且是进行替换而不需要挪动——也就是说,我们可以使用 二分查找 ,将每一个数字的插入时间优化到 O(logN),于是算法的时间复杂度就降低到了O(NlogN)。
下面给出java代码:
public class AscentSequence {
    public int findLongest(int[] A, int n) {
        int length = A.length;
        int[] B = new int[length];
        B[0] = A[0];
        int end = 0;
        for (int i = 1; i < length; ++i) {
            // 如果当前数比B中最后一个数还大,直接添加
            if (A[i] >= B[end]) { B[++end] = A[i]; continue;
            } 
            // 否则,需要先找到替换位置
            int pos = findInsertPos(B, A[i], 0, end); B[pos] = A[i];
        }
        for (int i = 0; i < B.length; ++i) {
            System.out.println(B[i]);
        }
        return end+ 1; }
    /**
     * 二分查找第一个大于等于n的位置
     */
    private int findInsertPos(int[] B, int n, int start, int end) {
        while (start < end) {
            int mid = start + (end - start) / 2;// 直接使用(high + low) / 2 可能导致溢出
            if (B[mid] < n) {
                start = mid + 1;
            } else if (B[mid] > n) {
                end = mid ;
            } else {
                return mid;
            }
        }
        return start;
    }
}

编辑于 2016-08-20 12:01:29 回复(10)
采用两个辅助数组dp[],help[],数组长度均为n.max_length表示最长递增子序列的长度。
dp[i]表示必须以A[i]结尾的最长递增子序列的长度,help[i]表示递增子序列长度为i+1的所有序列中结尾最小的值。其中dp[0]=1,help[0]=A[0].遍历数字序列A,更改dp[],help[]的值,若dp[i]>max_length,更新max_length的值。最后返回max_length。因为help[]是排好序的,所以在更新help[]时查找A[i]的位置时采用二分搜索。遍历数组+二分搜索更新,所以时间复杂度是O(nlogn)
例子:其中红线部分表示更新过程,当插入A[1]=1时,help[0]为2,比1大,所以更新为help[0]=1;当插入A[2]=4时,help[0]=1,比4小,所以更新help[1]=4.重复至遍历数字序列完成。


代码:
class AscentSequence {
public:
    int findLongest(vector<int> A, int n) {
        // write code here
        int dp[n];
        int help[n];
        int max_length=0,count=0;
        dp[0]=1;help[0]=A[0];
        for(int i=1;i<n;i++)                             //遍历数字序列
            {
            int right=count,left=0,middle;
            while(left<=right){ //   查找A[i]更新help[]时的位置
                middle=(left+right)/2;
                if(A[i]>=help[middle]){
                    left=middle+1;
                }else{
                    right=middle-1;
                }
            }
            help[left]=A[i];                        //更新help[]的值
            if(left>count)
                count=left;
            dp[i]=left+1;                     //更新dp[]的值
            if(dp[i]>max_length)       //更新最长递增子序列的长度
                max_length=dp[i];
        }
        return max_length;
    }
发表于 2015-08-07 13:03:08 回复(1)
寻找最长递增子序列,只需要维护一个递增序列即可,   该序列代表的size表示扫描到元素 i 为止最长的递增序列长度。
对于原数组中的每个元素的处理,我们用二分搜索找到它在该递增序列所处的合适位置,对递增序列进行更新。可以看下注释。

int findLongest(vector<int> A, int n) {
// write code here
if(n==0)
return 0;
vector<int> up;
up.push_back(A[0]);
for(int i=1;i<n;i++)
{
int low=0,high=up.size()-1;
int mid;
while(low<=high){
mid=low+(high-low)/2;
if(A[i]<up[mid])
high=mid-1;
if(A[i]==up[mid])
break;    //A[i]=up[mid]时,不用更新
if(A[i]>up[mid])
low=mid+1;
}
                //比序列中所有元素都小
if(high<0)
up[0]=A[i];
                //比序列中所有元素都大时
else if(low>=up.size())
up.push_back(A[i]);
                //位于序列元素最大值与最小值之间时,low的值是i元素的在递增序列中的合适位置,我们对这个位置的值进行更新(因为更新前A[i]<up[low]  但是A[i]>up[low-1]),保证递增序列中每个元素的值都是对应长度的最小值。
else if(up[mid]!=A[i])    
up[low]=A[i];
}
return up.size();
}
编辑于 2015-08-11 16:08:13 回复(1)
class AscentSequence {
public:
    int findLongest(vector<int> A, int n) {
        int dp[1000];
        for(int i=0;i<n;i++){
            dp[i]=1;
        }
        for(int i=1;i<n;i++){
            int tmax=1;
           for(int j=0;j<i;j++){
               if(A[j]<A[i]){
                   tmax=max(tmax,dp[j]+1);
               }
           }
            dp[i]=tmax;
        }
        int ans=1;
        for(int i=0;i<n;i++){
            ans=max(ans,dp[i]);
        }
        return ans;
    }
};

发表于 2018-02-19 16:28:38 回复(1)
import java.util.*;

public class AscentSequence {
    public int findLongest(int[] A, int n) {
        int[] dp=new int[n];
        int max=0;
        for(int i=0;i<n;i++){
            dp[i]=1;
            for(int j=0;j<i;j++){
                if(A[i]>A[j]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                    if(dp[i]>max)
                        max=dp[i];
                }
            }
        }
       return max;
    }
}

发表于 2017-07-30 11:33:25 回复(0)
package dp;
//时间复杂度O(n^2)
public class AscentSequence {
    public int findLongest(int[] arr, int n) {
    	int[] dp = new int[n];
    	dp[0] = 1;
    	int maxLen = 1;
    	for (int i = 1; i < n; i++) {
    		dp[i] = 1;
    		for (int j = 0; j < i; j++) {
    			if (arr[j] < arr[i] && dp[i] < dp[j]+1) {
    				dp[i] = dp[j]+1;
    				maxLen = Math.max(maxLen, dp[i]);
    			}
    		}
    	}
    	
    	return maxLen;
    }
}


发表于 2017-04-03 20:23:24 回复(3)

O ( n2 )
public int findLongest(int[] A, int n) {
        int[] f = new int[n];//用于存放f(i)值;
        f[0]=1;//以第a1为末元素的最长递增子序列长度为1;
        for(int i = 1;i<n;i++)//循环n-1次
        {
               f[i]=1;//f[i]的最小值为1;
               for(int j=0;j<i;j++)//循环i 次
               {
                      if(A[j]<A[i]&&f[j]>f[i]-1)
                             f[i]=f[j]+1;//更新f[i]的值。
               }
        }
        Arrays.sort(f);
        return f[n-1];
    }

O(nlogn)    参考网址 https://www.felix021.com/blog/read.php?1587
import java.util.*;

public class AscentSequence {
    public int findLongest(int[] A, int n) {
        int[] B = new int[n+1]; B[1] = A[0];
        int len=1,start=0,end=len,mid;
        for(int i = 1;i<n;i++){
        	if(A[i]>B[len]) {len++;B[len] = A[i];}
        	else{
        		start=1;end=len;
        		while(start<=end){
            	  mid=(start+end)/2;
            	  if(B[mid]<A[i]) start=mid+1;
            	  else end=mid-1;
              } B[start] = A[i]; 
        	}
        }
        return len;
    }
}

编辑于 2016-09-25 14:05:31 回复(0)

python只需要6行代码搞定,不多bb:

import bisect
class AscentSequence:
    def findLongest(self, A, n):

        res=[]
        for i in A:
            pos=bisect.bisect_left(res,i)
            if pos==len(res): res.append(i)
            else: res[pos]=i
        return len(res)
编辑于 2017-09-16 17:58:56 回复(0)

原文地址:https://blog.csdn.net/cooper20/article/details/80765897
共有四种思路

求解

### 方法 1 暴力搜索(超出时间限制)

算法
最简单的方法是尝试寻找所有递增子序列,然后返回递增子序列的最大长度。为此,我们使用递归函数lengthofLIS,该函数返回从当前元素(curpos)向前(包括当前元素)的LIS长度。每次函数调用时,考虑两种情况:

  1. 当前元素比LIS中的前一个元素大。这种情况下,我们可以将当前元素纳入LIS。然后求出包含当前元素后的LIS长度。同时,我们也求出不包含当前元素的LIS长度。最后返回两个长度的最大值。
  2. 当前元素小于LIS中的前一个元素。这种情况下,不能将当前元素放入LIS中。因此,我们返回不包含当前元素的LIS长度。
public class Solution {
    public int lengthOfLIS(int[] nums) {
        return lengthofLIS(nums, Integer.MIN_VALUE, 0);
    }
    public int lengthofLIS(int[] nums, int prev, int curpos) {
        if (curpos == nums.length) {
            return 0;
        }
        int taken = 0;
        if (nums[curpos] > prev) {
            taken = 1 + lengthofLIS(nums, nums[curpos], curpos + 1);
        }
        int nottaken = lengthofLIS(nums, prev, curpos + 1);
        return Math.max(taken, nottaken);
    }
}

复杂度分析

  • 时间复杂度:O(2^n)。递归数大小2^n。
  • 空间复杂度:O(n^2)。使用了n*n的数组内存。

方法 2 记忆化递归(超出空间限制)

算法
在上一个方法中,许多参数相同的递归过程被多次调用。通过将递归调用结果保存在一个二维记忆数组memo中,可以消除冗余的调用。memo[i][j]表示num[i]作为前一个元素放入/不放入LIS,并且num[j]作为当前元素放入/不放入LIS时的最长LIS。(memo[i][j] represents the length of the LIS possible using nums[i]nums[i] as the previous element considered to be included/not included in the LIS, with nums[j]nums[j] as the current element considered to be included/not included in the LIS.)。num表示所给定的数组。

ps:由暴力递归改写。递归函数可变参数 preIndex、curpos,无后效性,故memo[i][j]中缓存由特定递归过程(preIndex, curpos)计算出的值。考虑到元素的取值范围***,在上一个方法中使用的pre参数(表示LIS中的上一个元素的值)需要替换,这里使用preIndex表示该元素在nums数组中的位置。

public class Solution {
    public int lengthOfLIS(int[] nums) {
        // preIndex的取值范围[-1, nums.length - 1],-1表示无前缀。故长度为nums.length + 1,为了将下标为-1的值放入数组,元素整体向后移一位。
        int memo[][] = new int[nums.length + 1][nums.length];
        for (int[] l : memo) {
            Arrays.fill(l, -1);
        }
        return lengthofLIS(nums, -1, 0, memo);
    }
    public int lengthofLIS(int[] nums, int previndex, int curpos, int[][] memo) {
        // base case
        if (curpos == nums.length) {
            return 0;
        }
        // serach first
        if (memo[previndex + 1][curpos] >= 0) {
            return memo[previndex + 1][curpos];
        }
        // compute and ***
        int taken = 0;
        if (previndex  nums[previndex]) {
            taken = 1 + lengthofLIS(nums, curpos, curpos + 1, memo);
        }
        int nottaken = lengthofLIS(nums, previndex, curpos + 1, memo);
        memo[previndex + 1][curpos] = Math.max(taken, nottaken);
        return memo[previndex + 1][curpos];
    }
}

复杂度分析

  • 时间复杂度:O(n^2),递归树的大小为n^2。
  • 空间复杂度:O(n^2),memo数组的吊销为n*n。

方法 3 动态规划(通过)

算法
动态规划方法依赖于这样一个事实——以i元素结尾的最长子序列不依赖于其后续元素。因此,如果已知以i元素结尾的LIS长度,可以求出以i+1元素结尾的LIS长度(通过向前搜索,尝试将i+1元素追加至其后)。
创建数组dp来存储相关数据。dp[i]表示以索引i元素作为结尾的子序列的最大长度。为了求解dp[i],尝试将当前元素(nums[i])追加到每一个既有的递增子序列中,使得添加完当前元素后的新序列仍然是递增序列,若无法添加至仍以既有子序列,则以i元素结尾的LIS长度为1。dp[i]的表达式为:

dp[i] = max(dp[j]) + 1, 0 nums[j]

即,对于dp[i],求nums[i]结尾的最长递增子序列,在nums[0..i-1]中选出比nums[i]小且长度最长(dp[j] max)的。

最后,dp[i]的最大值即为所求答案,

LIS = max(dp[i]), 0 <= i < n

ps:原著英文较差,此处意译。

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

复杂度分析

  • 时间复杂度:O(n^2),两个for循环。
  • 空间复杂度:O(n)。

方法 4 动态规划 + 二分查找(通过)

算法
方法3花费了大量时间寻找最大dp[j]上(第二个for循环),如果dp[]是一个递增数列,那么我们可以使用二分查找进行优化,使得整个算法的复杂度下降到O(nlogn)。方法3中dp[i]保存了以nums[i]元素结尾的LIS长度,这里我们使用dp[i]保存所有长度为i+1的递增子序列中末尾元素的最小值。根据这个最小值,可以判断num数组中的后续元素是否可以追加到既有IS中以形成更长的IS。由于dp数组是递增的,所以可以使用二分查找。
举例:

nums: 2 1 5 3 6 4 8 9 7
dp[]: 2.........// 遍历至nums[0],当前长度为1的子序列末尾的最小值为2.
dp[]: 1.........// 遍历至nums[1],nums[1]
dp[]: 1 5.......// nums[2],nums[2]
dp[]: 1 3.......// dp[0]
dp[]: 1 3 6.....// num[4] > dp[2],可形成长度为3的子序列。
dp[]: 1 3 4.....// dp[1]
dp[]: 1 3 4 8...// num[6] > dp[2],形成更长的子序列。
dp[]: 1 3 4 8 9.// 形成更长的子序列
dp[]: 1 3 4 7 9.// dp[2]
最终,dp.size = 5,表示LIS=5,且所有该长度序列中最小以9结尾。

public class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int len = 0;
        for (int num : nums) {
            int i = Arrays.binarySearch(dp, 0, len, num);
            if (i < 0) {
                i = -(i + 1);
            }
            dp[i] = num;
            if (i == len) {
                len++;
            }
        }
        return len;
    }
}

复杂度分析

  • 时间复杂度:O(nlogn),二叉搜索花费logn,被调用了n次。
  • 空间复杂度:O(n)

参考:
https://leetcode.com/problems/longest-increasing-subsequence/solution/

编辑于 2018-06-21 20:53:19 回复(0)
classAscentSequence {
public:
    intfindLongest(vector<int> A, intn) {
        if(n==0) return0;
        vector<int> hash(n);
        intans=0;
        for(inti=0;i<n;i++){
            hash[i]=1;
            for(intj=i-1;j>=0;j--){
                if(A[i]>A[j]){
                   if(hash[j]+1>hash[i]){
                       hash[i]=hash[j]+1;
                       if(hash[i]>ans)
                           ans=hash[i];
                   }
                     
                }
            }
        }
        returnans;
}
};
编辑于 2016-08-05 11:48:18 回复(0)
classAscentSequence {
public:
    intfindLongest(vector<int> A, intn) {
        // write code here
        vector<int> B;
        intmax = 0;
        for(inti=0;i<n;i++){
            B.push_back(1);
            for(intj=i-1;j>=0;j--)
            {
                if(A[j]<A[i]) B[i] = B[j]>=B[i]?B[j]+1:B[i];
            }
            max = max>B[i]?max:B[i];
        }
        returnmax;
    }
};

程序借助辅助vector<int> B,B中元素记录A中对应元素当前最大升序值,B[i]初始化为1,遍历A中元素来更新B[i]的值,max记录最大升序长度。
有不了解的地方请回复!!!
发表于 2015-08-06 18:19:25 回复(5)
public class AscentSequence {
    public int findLongest(int[] arr, int n) {
        // 时间复杂度 O(n*lgn)
        List<Integer> list = new ArrayList<>(n);
        for(int i:arr){
            if(list.isEmpty()||i>list.get(list.size()-1))
                list.add(i);
            else
                list.set(getIndex(list,i,0,list.size()-1),i);
        }
        return list.size();
    }
    public int getIndex(List<Integer> list,int target,int L,int R){
        while(L<R){
            int mid = L+((R-L)>>1);
            if(list.get(mid)<target)
                L = mid+1;
            else
                R = mid;
        }
        return L;
    }
}
编辑于 2019-01-18 20:59:16 回复(0)
bisect模块
import bisect
class AscentSequence:
    def findLongest(self, A, n):
        res=[]
        for val in A:
            index=bisect.bisect_left(res,val)
            if index==len(res):
                res.append(val)
            else:
                res[index]=val
        return len(res)

class AscentSequence:
    def findLongest(self, A, n):
        temp=[10**10]*n
        temp[0]=A[0]
        res=[1]
        for i in range(1,n):
            pos=self.get_index(temp,A[i])
            res+=[pos+1]
            temp[pos]=A[i]
        return max(res)
    def get_index(self,nums,target):
        low,high=0,len(nums)-1
        pos=0
        while low<high:
            mid=(low+high)//2
            if nums[mid]<target:
                low=mid+1
            else:
                high=mid
                pos=high
        return pos


发表于 2018-07-31 09:48:49 回复(0)
class AscentSequence {
public:
    int findLongest(vector<int> A, int n) {
        int B[n+1];
        B[1] = A[0];
        int l=1,s=0,e=l,m;
        for(int i=1;i<n;i++)
        {
            if(A[i]>B[l])
            {
                l++;
                B[l] = A[i];             }else{                 s = 1;                 e = l;                 while(s<=e)                 {                     m = (s+e)/2;                     if(B[m]<A[i])                         s = m+1;                     else                         e = m-1;                 }                 B[s] = A[i];             }         }         return l;
    }
};

发表于 2017-10-21 01:11:06 回复(0)
典型动态规划题目。
对于arr,生成dp,dp[i]表示在必须以arr[i]这个数结尾的情况下,arr[o...i]中的最大递增子序列长度。

dp[0]=1
对于dp[i],所有比arr[i]小的数都可以作为倒数第2个数,其中,哪个数的dp最大,则将其作为倒数第2个数
dp[i]=max{dp[j]+1 (0<=j<1,arr[j]<arr[i])}
返回dp中最大的数

class AscentSequence {
public:
    int findLongest(vector<int> A, int n) {
        // write code here
        vector<int> dp(n,0);
        int res=0;
        dp[0]=1;
        for(int i=0;i!=n;i++){
            int max=0,j=0;
            while(j<i){
                if(A[j]<A[i]&&dp[j]>max)
                    max=dp[j];
                j++;
            }
            dp[i]=max+1;
        }
        for(int i=0;i!=n;i++)
            if(res<dp[i])
                res=dp[i];
        return res;
    }
};


编辑于 2017-10-11 14:35:02 回复(0)
class AscentSequence {
public:
    int findLongest(vector<int> A, int n) {
        if(n==1)
            return 1;
        vector<int> maxLen(n,1);
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(A[i]>A[j])
                    maxLen[i]=max(maxLen[i],maxLen[j]+1);
            }
        }
        int val=maxLen[0];
        for(int i=0;i<n;i++)
        {
            if(maxLen[i]>val)
                val=maxLen[i];
        }
        return val;
    }
};

发表于 2017-06-26 17:00:10 回复(1)
package alex.suda.dp;

import java.util.Scanner;

public class test1 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNext()) {
			int n = scanner.nextInt();
			int[] A = new int[n];
			for (int i = 0; i < n; i++) {
				A[i] = scanner.nextInt();
			}
			System.out.print(findLongest(A, n));
		}
	}

	public static int findLongest(int[] A, int n) {
		// 以[2,1,4,3,1,5,6]为例。使用i来表示当前遍历的位置:
		// i = 1 时,最长递增序列为{1} ,序列长度为1
		// i = 2时,1 < 2 所以得丢弃2 重新建立最长递增序列{1},序列长度为1
		// i = 3时,4>2,4>1 最长递增序列为{2,4} {1,4},长度为2
		// 以此类推,可得:d[i+1] = max{1,d[k]+1},其中对于所有的k<= i ,A[i+1] > A[k] 
		// d[i] 表示A数组的前i个元素当中,最长递增序列的长度
		int[] d = new int[n];
		for (int i = 0; i < n; i++) {
			d[i] = 1; // 初始化默认长度
			for (int j = 0; j < i; j++) { // 前面最长的序列
				if (A[i] > A[j] && d[j] + 1 > d[i]) { // 增加了当前的数之后,大于原来的长度,就更新
					d[i] = d[j] + 1;
				}
			}
		}
		int maxDis = Integer.MIN_VALUE;
		for(int i=0;i<n;i++){
			if(d[i] > maxDis){
				maxDis = d[i];
			}
		}
		return maxDis;
	}
}


发表于 2016-10-05 21:57:14 回复(0)
import java.util.*;

public class AscentSequence {
    public int findLongest(int[] A, int n) {
        // write code here
        int[] dp = new int[n];
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; ++i) {
            if (i == 0) {
                dp[i] = 1;
            } else {
                dp[i] = 1;
                for (int j = i - 1; j >= 0; --j) {
                    if (A[j] < A[i]) {
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
            }
            max = Math.max(dp[i], max);
        }
        return max;
    }
}

发表于 2016-08-29 18:40:11 回复(0)
class AscentSequence {
public:
    int findLongest(vector<int> v, int n) {
        if(n == 0)
            return 0;
        std::vector<int> tmp;
        for (int i = 0; i < n; ++i)
        {
            auto iter = std::lower_bound(tmp.begin(), tmp.end(), v[i]);
            if(iter == tmp.end())
                tmp.push_back(v[i]);
            else
                *iter = v[i];
        }

        return tmp.size();
    }
};
发表于 2016-08-22 23:08:33 回复(0)
//时间复杂度o(n2)
class AscentSequence {
public:
    int findLongest(vector<int> A, int n) {
        vector<int> vec(n,1);
        int R=0;
        for(int i=1;i<n;i++){
            for(int j=i-1;j>=0;j--){
                if(A[j]<A[i]&&vec[j]+1>vec[i])
                    vec[i]=vec[j]+1;
            }
            if(vec[i]>R)
                R=vec[i];
        }
       return R;
    }
};

发表于 2016-08-15 14:51:02 回复(0)

问题信息

难度:
74条回答 31434浏览

热门推荐

通过挑战的用户

查看代码