题解 | #递减种子序列#

import java.util.*;


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

    }
}

本题考察的知识点主要是动态规范，所用编程语言为java.动态规范的核心在于状态转移方程的建立。

我觉得最差情况就是非递减序列，此情况结果为1，此为数组边界条件，状态转移方程可以从如下代码可以看出

for (int i = 1; i < seeds.length; i++) {

for (int j = i - 1; j >= 0; j--) {

if (seeds[i] < seeds[j]) {

arr[i] = Math.max(arr[i], arr[j] + 1);

}

}

}

最后答案为arr数组中的最大值，arr数组中每个值都是原序列在该位置的最长递减子序列长度。