Java机试题*：走梅花桩，最长上升子序列（动态规划）

import java.util.Arrays;
import java.util.Scanner;

/**
 * 
   *   走梅花桩，最长上升子序列
   *   状态设计：F [ i ] 代表以 A [ i ] 结尾的 LIS 的长度
   *   状态转移：F [ i ] = max { F [ j ] + 1 ，F [ i ] } (1 <= j <  i，A[ j ] < A[ i ])
   *   边界处理：F [ i ] = 1 (1 <= i <= n)
   *   动态规划的状态转移方程有时不好总结，需要理解和总结
 *
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int num = sc.nextInt();
            // 构建数组
            int[] arr = new int[num];
            for (int i = 0; i < num; i++) {
                arr[i] = sc.nextInt();
            }
            // int数组元素默认值为0，将数组都初始化为1，因为起点本身算一步
            // 定义ret[i]来表示前i个数以arr[i]结尾，的最长上升子序列长度。ret[0] = 1
            int[] ret = new int[num];
            Arrays.fill(ret, 1);
            for (int i = 0; i < num; i++) {
                // 计算i对应的最长上升子序列长度，需要从ret[0]开始遍历i个，用于计算i
                for (int j = 0; j < i; j++) {
                    /*
                     * eg: 2 5 1 5 4 5 
                     * ret[0] = 1, 2 
                     * ret[1] = 2, 2 5 
                     *     5 > 2 Math.max(ret[1], ret[0] +    1) = 2 
                     * ret[2] = 1 
                     *     2,5 > 1 
                     * ret[3] = 2, 2 5 
                     *     5 > 2 Math.max(ret[3], ret[0] + 1) = 2 
                     *  5 > 1 Math.max(ret[3], ret[2] + 1) = 2
                       *   故: 总结出状态转移方程：ret[i] = Math.max(ret[i], ret[j] + 1)
                     */
                    if (arr[j] < arr[i]) {
                        ret[i] = Math.max(ret[i], ret[j] + 1);
                    }
                }
            }
            // 排序，默认升序，则最后一个是最大的
            Arrays.sort(ret);
            System.out.println(ret[num - 1]);
        }
    }
}

参考链接：https://blog.nowcoder.net/n/0728771afd634de9bc00426d7b7f133e?f=comment

参考链接：https://blog.csdn.net/lxt_Lucia/article/details/81206439

参考链接：https://www.nowcoder.com/practice/24e6243b9f0446b081b1d6d32f2aa3aa?tpId=37&&tqId=21326&rp=1&ru=/ta/huawei&qru=/ta/huawei/question-ranking