题解 | 最长不下降子序列 c#

using System;
using System.Collections.Generic;
using System.Linq;
public class Program {
    public static void Main() {
        int.TryParse(Console.ReadLine(), out int num);
        List<int> numsLst = Console.ReadLine().Split(' ').Select(x => int.Parse(
                                x)).ToList();
        Console.WriteLine(LongestNonDecreasingSubsequence(numsLst));
    }
    static int LongestNonDecreasingSubsequence(List<int> lst) {
        if (lst.Count == 1) {
            return 1;
        } else {
            //题解中都是用二分查找+贪心，我这里用最基本的解法，纯动态规划
            //用一个dp来储存列表中每一步的最长不下降子序列
            int[] dp = new int[lst.Count];

            for (int i = 0; i < lst.Count;
                    i++) { //每个位置的最长不下降子序列长度至少为1
                dp[i] = 1;
            }

            for (int i = 0; i < lst.Count; i++) {
                for (int j = 0; j < i; j++) {
                    if (lst[j] <
                            lst[i]) { //发现有之前的数字比当前数字小,说明把之前数字到当前数字之间的数字都去掉也能构成一个不下降子序列，所以当前的dp[i]可以等于 dp[j] + 1，当然这可能不是最优解，所以j要一直遍历到i前面，找出最优解
                        //然后就要对比，因为可能有多个 j 满足条件，我们要选能形成最长序列的那个 j，所以要用Math.Max
                        dp[i] = Math.Max(dp[i], dp[j] + 1);
                    }
                }
            }
            return dp.Max();
        }
    }
}