披萨大叔

LIS问题，O(N ² )解法就不说了，下面说下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)

Coder_ZF

采用两个辅助数组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)

scut_huajian

寻找最长递增子序列，只需要维护一个递增序列即可，该序列代表的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)

Miyagi11

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)

MAK33

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)

Iandme

O ( n² )

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

华科平凡

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长度。每次函数调用时，考虑两种情况：

当前元素比LIS中的前一个元素大。这种情况下，我们可以将当前元素纳入LIS。然后求出包含当前元素后的LIS长度。同时，我们也求出不包含当前元素的LIS长度。最后返回两个长度的最大值。
当前元素小于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)

OnePiece~~


	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)

OOACMer

  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)

C/C++

nbgao

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)

蓝魔4

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)

Alex-大伟

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)

Java

JustYoung

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)

cristiano-dua

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)

fight灬奋斗

//时间复杂度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)

何恺明的小迷妹

//C++           O(n^2)解
//时间复杂度为0(n^2)
class AscentSequence {
public:
    int findLongest(vector<int> A, int n) {
        // write code here
		vector<int>vi(n);
		for(int i = 0; i < n; i++)
            vi[i] = 1;

        for(int i = 1;i < n; i++)
            for(int j = 0;j < i;j++){
                if(A[i] > A[j]){
                    vi[i] =vi[i]>(vi[j]+1)?vi[i]:vi[j]+1;
                }
            }
        sort(vi.begin(),vi.end());
        return vi[n-1];
    }
};

发表于 2016-07-21 15:10:22 回复(0)

最长递增子序列

求解

方法 2 记忆化递归（超出空间限制）

方法 3 动态规划（通过）

方法 4 动态规划 + 二分查找（通过）

问题信息

热门推荐

通过挑战的用户

相关试题