题解 | #递减种子序列#

知识点：动态规划

对于动态规划类的题目，一个难点是定义出状态，另一个难点是找出状态转移方程。这道题中，我们可以定义dp[i]为i位置可以得到的最长递减序列长度，当我们获得了0到i-1位置的最长递减序列长度时，对于i位置来说，我们只需要依次判断是否能与前序列形成递减关系，若可以，则最长递减序列的长度+1，作为当前位置的最长序列递减长度。同时，遍历每个位置能够达到的最长递减序列长度，最大值即为答案。

Java题解如下

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param seeds int整型一维数组 
     * @return int整型
     */
    public int lengthOfLIS (int[] seeds) {
        // write code here
        int n = seeds.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int max = 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);
                    max = Math.max(max, dp[i]);
                }
            }
        }
        return max;
    }
}