题解 | #递减种子序列#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param seeds int整型一维数组
     * @return int整型
     */
    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;
    }
}

本题知识点分析：

1.动态规划

2.API函数

3.数组遍历

本题解题思路分析：

1.dp数组是什么？每个索引时刻，最长的递减序列长度

2.dp数组公式-> dp[i] = Math.max(dp[i], dp[j] + 1);

3.dp数组初始化 Arrays.fill(dp, 1);

4.dp数组遍历顺序，从前往后，判断是否递减，这边用O(n2)穷举

5.返回maxLength即可

本题使用编程语言: Java