题解 | #递减种子序列#

题目考察的知识点

考察动态规划

题目解答方法的文字分析

构建dp数组，dp[i]表示该位置上递减序列的最大长度，起始状态全为1，表示这个位置上的数他本身就构成了一个递减序列，长度为1。随后双重循环检查每一个序列。dp[i] = Math.max(dp[i], dp[j] + 1)为状态转移方程，并且只有当构成递减条件的时候才触发，即后一个位置数小于前一个位置的时候。

本题解析所用的编程语言

使用Java语言解答

完整且正确的编程代码

import java.util.*;


public class Solution {
    public int lengthOfLIS(int[] seeds) {
        int n = seeds.length;
        if (n == 0) return 0;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);  //起始状态下数组全为1
        int maxLength = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (seeds[j] > seeds[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLength = Math.max(maxLength, dp[i]);
        }
        return maxLength;
    }
}