题解 | #递减种子序列#

知识点

动态规划

解题思路

dp数组i表示以i为结尾的最长子序列，

遍历数组seeds，要找到前面第一个大于seeds[i]的seeds的下标j，dp[i]就是前面的一个大于seed[i]的下标j的dp[j] + 1了，如果没有找到j，说明前面没有大于seeds[i]的，则dp[i]等于1。记录其中最大的de[i]返回。

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];
        int ans = 1;
        dp[0] = 1;
        for (int i = 0; i < n; i++){
            int j = i - 1;
            for(; j >= 0; j--){
                if(seeds[i] < seeds[j]){
                    dp[i] = dp[j] + 1; 
                    ans = Math.max(ans,dp[i]);
                    break;
                }
            } if(j == -1){
                dp[i] = 1;
                ans = Math.max(ans,dp[i]);
            }
        }
        return ans;
    }
}