算法分析

第二问
贪心流程：
从前往后枚举每个数，对于每个数：

• 情况1：如果现有的子序列的结尾都小于当前前数，则创建新子序列

• 情况2：将当前数放到结尾大于等于它的最小的子序列后面

注意：代码中g[]数组表示从小到大存放所有子序列的结尾

证明：
A表示贪心算法得到的序列个数，B表示最优解

• B <= A (最优解得到的个数一定比其他算法得到的个数少)

• A <= B,调整法

• 假设最优解对应的方案和当前方案不同，找到第一个不同的数，最优解和贪心法第一个不同的数一定可以进行调整交换，且交换该数使得序列个数不会增加，继续寻找下一个不同的数，进行相同的操作，由数学归纳法可知，直到最后一个不同的数为止，依然能够进行调整交换，且不会增加序列个数，因此A <= B
  可证明出A == B

时间复杂度 $O(n^2)$

参考文献

算法提高课

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main{
    static int N = 1010;
    static int n;
    static int[] q = new int[N];
    static int[] g = new int[N];//从小到大存放所有子序列的结尾
    static int[] f = new int[N];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        n = s.length;
        for(int i = 0;i < s.length;i ++)    q[i] = Integer.parseInt(s[i]);
        int res = 0;
        for(int i = 0;i < n;i ++)
        {
            f[i] = 1;
            for(int j = 0;j < i;j ++)
            {
                if(q[j] >= q[i])
                    f[i] = Math.max(f[i], f[j] + 1);
                res = Math.max(res, f[i]);
            }
        }
        System.out.println(res);

        int cnt = 0;//表示当前有多少个序列
        for(int i = 0;i < n;i ++)
        {
            int k = 0;
            while(k < cnt && g[k] < q[i]) k ++;
            g[k] = q[i];
            if(k >= cnt) cnt ++;
        }
        System.out.println(cnt);
    }
}