题解 | #递减种子序列#
递减种子序列
https://www.nowcoder.com/practice/708a3a8603274fc7b5732c5e73617203
知识点：动态规划
对于动态规划类的题目，一个难点是定义出状态，另一个难点是找出状态转移方程。这道题中，我们可以定义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;
}
}
真有趣游戏公司福利 33人发布
