最长不降序子序列

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.*;
public class Main {
    static Scanner sc = new Scanner(System.in);
    static int n = sc.nextInt();
    static int a[] = new int[n];
    static int b[] = new int[100];
    static int manxlen = 0;

    static void dfs(int now,int pos,int count,int a[]){
        if(now >= n){
            if(count > manxlen){
                manxlen = count;
                return;
            }
        }
        for(int i = now;i < n;i++){
            if(pos == 0 || b[pos - 1] <= a[i]){
                b[pos] = a[i];
                count++;
                dfs(i+1,pos+1,count,a);
                count--;
            }
        }



    }

    public static void main(String[] args) throws IOException {
        for(int i = 0;i <n;i++){
            a[i] = sc.nextInt();
        }
        if(a.length == 0){
            System.out.println(0);
        }else{
            manxlen = 0;
            dfs(0,0,0,a);
            System.out.println(manxlen);
        }


    }

}

通过昨天的琢磨，现在写递归方法就比以前多有了一些思路。第一是自己想到了需要用一个数组来计数，但是没有想到是需要到两个数组。一个数组a是题目要求输入的数组，一个数组b是用来存放升序子序列的数组。这里说明一个问题，自己琢磨了一下其实子序列是可以挑出来的，例如1,7,2,5，4,8；那么子序列可以是1258，长度为4.

那么首先就要定一个maxlen了，就是最长的子序列长度，然后接下来是dfs方法，参数是数组a，当前的元素now，当前的元素下标pos，技术count；首先要有一个出口，也就是如果now大于或者等于原数组的长度那么就开始判断是否符合条件。接下来是for循环，判断条件是pos=0或者是b[pos - 1]小于a[i]的话（比如b[0]<=a[1]），那么就可以成立，count++，然后继续递归，如果递归之后的条件不符合，那么就return，且在递归条件后，count--，也就是复原，就可以了。