入门例子

找出最长递增子序列
eg: [1,5,2,4,3]

简单想法- 暴力枚举

从1 出发，开始找 最长递增子序列
1 5 没了

从1 出发，第二个数选择2开始

依次类推，扫描每个数，得到如下 递增树图

然后呢，从2 开始，从5开始，依次计算 最长序列长度

代码实现

/**
 找出最长递增子序列
eg: [1,5,2,4,3]


 暴力枚举

 */

public class test2 {
    public static int L (int[] nums, int i){

        if (i == nums.length - 1) return 1;

        int maxLen = 1;
        for (int j = i + 1; j < nums.length; j++){
            if (nums[j] > nums[i]){
                maxLen  = Math.max(maxLen,L(nums,j) + 1);
            }
        }
        return maxLen;
    }

    public static int lengthOfL(int[] nums){
        int maxLen = 0;
        for(int i = 0; i < nums.length; i++){
            maxLen = Math.max(maxLen,L(nums,i));
        }
        return maxLen;
    }


    public static void main(String[] args) {
        int[] nums = {1,5,2,4,3};
        System.out.println(lengthOfL(nums));
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

时间复杂度
数组长度 为 n
存在 2的n次方个组合 的 子序列

每个子序列，需要遍历 n次

改进暴力循环

设置字典，避免重复节点计算

public class test2 {

    public static int L (int[] nums, int i, HashMap memo){
        if (i == nums.length - 1) return 1;
        if (memo.containsKey(i)) return (int) memo.get(i);

        int maxLen = 1;
        for (int j = i + 1; j < nums.length; j++){
            if (nums[j] > nums[i]){
                maxLen  = Math.max(maxLen,L(nums,j, memo) + 1);
            }
            memo.put(i,maxLen);
        }
        return maxLen;
    }

    public static int lengthOfL(int[] nums){
        HashMap<Integer,Integer> memo = new HashMap<>();

        int maxLen = 0;
        for(int i = 0; i < nums.length; i++){
            maxLen = Math.max(maxLen,L(nums,i,memo));
        }
        return maxLen;
    }


    public static void main(String[] args) {
        int[] nums = {1,5,2,4,3};
        System.out.println(lengthOfL(nums));
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

避免重复节点的计算，从而加速 计算的过程。
使用 空间 换时间。
递归树的剪枝

思路整理

从1开始出发，长度为1
从1开始出发的 最长长度 = 1 + 从后面元素开始出发的其中一个最长步数
从2开始出发的 最长长度 = 1 + 从后面元素开始出发的其中一个最长步数
…依次递归

下面 L（0 ）到L(4) 其中括号里面的数字 是下标的意思

L(4) 为1
因为 这个下标4，是第5个元素，也是最后一个元素，它的步长只能为1.

import java.util.HashMap;

/**
 找出最长递增子序列
eg: [1,5,2,4,3]


 暴力枚举

 */

public class test2 {

    public static int lengthOfL(int[] nums){
        int n = nums.length;

        int[] L = new int[n];

        for (int a = 0; a < n; a++){
            L[a] = 1;
        }


        // loop through from the end to the begining
        for (int i = n - 1; i >= 0; i--){ // i: 4 3 2 1 0
            for (int j = i + 1; j < n; j++){
                if (nums[j] > nums[i]){
                    L[i] = Math.max(L[i],L[j] + 1);
                }
            }
        }

        int max= L[0];
        for (int b: L){
            if (b > max) max = b;
        }

        for (int x: L){
            System.out.print(x  + " ");
        }

        return max;

    }


    public static void main(String[] args) {
        int[] nums = {1,5,2,4,3};
        System.out.println(lengthOfL(nums));
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52