题目 #

题目描述 #

子序列是原数组中一些元素的有序集合，这些元素按照它们在原数组中的出现顺序进行选择，但不一定要相邻。现在给定一个数组 array，需要你找出该数组的最长增长子序列的长度。

输入描述 #

第一行是一个整数 N，表示后续会有 N 行输入。每个数组占一行。

输出描述 #

对于输入的每个数组，你需要输出其该数组最长子序列的长度。每个输出占一行。

输入示例 #

1
[1,5,122,34,45,232,342,34]

输出示例 #

提示信息 #

以测试数据为例：[1,5,122,34,45,232,342,34]，把其中所有的增长子序列罗列出来。 

形成了： 

 第一个子序列：[1,5,122] 

 第二个子序列：[34,45,232,342]

 第三个子序列：[1,5,122,232,342] 

 第四个子序列：[1,5,34,45,232,342] 

 在这四个序列中，第四个序列最长，所以这个例子中，最长增长子序列的长度为 6

1 <= N < 100;
1 <= array.length < 1000.

解答 #

方法1 动态规划 #

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out=new PrintWriter(System.out);
        String line;
        line=in.readLine();
        int n=Integer.parseInt(line);
        while(n>0){
            line=in.readLine();
            String temp=line.substring(1,line.length()-1);
            String[] arrStr=temp.split(",");
            int[] arr=new int[arrStr.length];
            for(int i=0;i<arr.length;i++){
                arr[i]=Integer.parseInt(arrStr[i]);
            }
           
            int maxLen=1;
            int[] dp=new int[arr.length];
            Arrays.fill(dp,1);
            for(int i=1;i<arr.length;i++){
                for(int j=0;j<i;j++){
                    if(arr[j]>=arr[i])continue;
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
                maxLen=Math.max(dp[i],maxLen);
            }
            out.println(maxLen);
            n--;
        }
        out.flush();
    }
}

使用动态规划进行求解：

dp[i]代表截止到i的最短子序列的长度

对于当前的num[i]来说，遍历i之前的全部num[k]：

如果num[k]>=num[i]，如果考虑了dp[k]，不是严格递增的序列，不可以
如果num[k]<num[i]，证明是小的，可以进行比较了，重复比较每一个出现的dp[i]，dp[i]=max(dp[i],dp[k]+1)

方法2 贪心 #

import java.io.*;
import java.util.*;
 
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out=new PrintWriter(System.out);
        String line;
        line=in.readLine();
        int n=Integer.parseInt(line);
        while(n>0){
            line=in.readLine();
            String temp=line.substring(1,line.length()-1);
            String[] arrStr=temp.split(",");
            int[] arr=new int[arrStr.length];
            for(int i=0;i<arr.length;i++){
                arr[i]=Integer.parseInt(arrStr[i]);
            }
            int len=1;
            int[] dp=new int[arr.length+1];
            dp[1]=arr[0];
            for(int i=1;i<arr.length;i++){
                if(arr[i]>dp[len]){
                    len+=1;
                    dp[len]=arr[i];
                }else{
                    int end=len;
                    int start=1;
                    int pos=0;
                    while(end>=start){
                        int mid=(end+start)/2;
                        if(dp[mid]<arr[i]){
                            pos=mid;
                            start=mid+1;
                        }
                        else{
                            end=mid-1;
                        }
                    }
                    dp[pos+1]=arr[i];
                }
            }
            out.println(len);
            n--;
        }
        out.flush();
    }
}

主要思路：

让增长的序列尽可能的慢速增长。

初始化一个数组d[i]代表，这个序列中长度为i的序列，最后一个值的大小，例如d[3]=4，代表的含义是，对于长度为3的序列，最后一个值的最小值是4，比如长度为3的序列，可能有1,2,4 1,4,5 1,8,9，其中出现的第三个值（也就是最后一个位置）的最小值是4。
对于d[]这个数组来说，其必然是递增排序的，如果不是递增排序的话，例如d[1]=1，d[2]=1，(其中d[2]代表序列2长度的序列最后一个为1，证明可能存在0,1这样的序列，这样d[1]记录的就应该是d[1]=0，而不是dp[1]=1)，这种情况显然不符合d[i]数组的定义。
设len为最长增长子序列的长度。
- 遍历整个原来的数组，如果num[i]>d[len]，证明这个数组是更大的，并且比当前长度len的序列的最后一个值还要大，说明这个数可以充当为d[len+1]的值，也就是len+1长度的最后一个位置的最小值，并且将len++。
- 如果出现num[i]<d[len]的情况，证明现在的num肯定是某一个长度i的增长子序列中的一个最小值，要替换掉现在长度为i的d[i]，由于前面证明说d[]是一个单调递增的数组，因此可以使用二分查找，寻找一个值d[j-1]<num[i]<d[j]，在找到这个位置之后，将值插入到d[j]=num[i]上。

一定要注意二分查找的pos的写法：

int end=len;
int start=1;
int pos=0;
while(end>=start){
    int mid=(end+start)/2;
    if(dp[mid]<arr[i]){
        pos=mid;
        start=mid+1;
    }
    else{
        end=mid-1;
    }
}
dp[pos+1]=arr[i];