动态规划算法

动态规划算法

定义dp[i]为第i个数在前i中按顺序排列的下标
    dp[i] = max(dp[i-1])+1
    其中:0 =< j < i
         arr[j] < arr[i]

public static int lengthOfLIS(int[] nums) {
    if (nums.length == 0) {
        return 0;
    }
    // 第i个数在前i中按顺序排列的下标
    int[] dp = new int[nums.length];
    dp[0] = 1;
    // 初始化最长上升子序列长度
    int maxLen = 1;
    for (int i = 1; i < nums.length; i++) {
        // 初始化i个数的下标
        int location = 0;
        // 第i个数以前i-1个数进行比较
        for (int j = 0; j < i; j++) {
            // 第i个数，比j个数大
            if (nums[i] > nums[j]) {
                // 得到前i-1个的最大下标
                location = Math.max(dp[j], location);
            }
        }
        dp[i] = location + 1;
        maxLen = Math.max(dp[i], maxLen);
    }
    return maxLen;
}

最长上升子序列