【dfs && 记忆化搜索】最长严格递增子数组的长度-递归实现

给定一个整数数组 nums，我们需要找出其中最长的严格递增非空子数组，并返回其长度，要求用递归实现。

输入示例：nums = [1, 4, 3, 3, 2]输出结果：2

解释：在 nums 中，严格递增的子数组有：[1], [2], [3], [3], [4], [1, 4]。最长的严格递增子数组的长度为 2

考虑递归逆序打印数组中的数字，如何实现。

     public static void main(String[] args) {
        int[] a = {1,2,3,4,5,2};
        print(a,0);
    }
	
	 public static void print(int[] a,int i) {
        if(i==a.length) return;
        print(a,i+1);
        System.out.print(a[i]+" ");
    }

上面打印结果是：2 5 4 3 2 1.

所以找最长递增子数组递归处理，按照递归打印则可以看到到达5的时候，返回通过和它前面的数字进行比较 可以计算出以5开始的最长递增子数组长度是1，递归回到4，用5的结果，可以算出长度是2，依次回到1，长度是5. 代码如下：

    public static void main(String[] args) {
        int[] a = {1,2,3,4,5,2};
        longestIncreasingSubArray(a,0,null);
    }

    public static int longestIncreasingSubArray(int[] a,int i,Integer from){
        if(i==a.length) return 0;
        if(from!=null&&from>=a[i]) return 0;
        int length = longestIncreasingSubArray(a,i+1,a[i])+1;
        System.out.println("a[i]="+a[i]+" length="+length);
        return length;
    }

以上答案：

a[i]=5 length=1

a[i]=4 length=2

a[i]=3 length=3

a[i]=2 length=4

a[i]=1 length=5

可以看出以a[i]为起始节点的最长递增子数组的长度在一次递归遍历过程中都可以算出来。所以此时可以用一个记忆化数组记录每个位置为子数组起始位置的最长递增子数组长度，避免后续重新从这个位置进行计算。代码进化成：

public static void main(String[] args) {
        int[] a = {1,2,3,4,5,2};
        int[] memo=new int[a.length];
        int max=0;
        for(int i=0;i<a.length;i++){
            if(memo[i]>0) continue;
            int length=longestIncreasingSubArray(a,i,memo,null); //以i为子数组开始位置能够达到的最长递增子数组的长度
            max=Math.max(max,length);
        }
        System.out.println(Arrays.toString(memo));
        System.out.println("max length="+max);
    }

    public static int longestIncreasingSubArray(int[] a,int i,int[] memo,Integer from){
        if(i==a.length) return 0;
        if(memo[i]>0) return memo[i];
        if(from!=null&&from>=a[i]) return 0;
        int length = longestIncreasingSubArray(a,i+1,memo,a[i])+1;
        System.out.println("a[i]="+a[i]+" length="+length);
        memo[i]=length;
        return memo[i];
    }

程序打印：

a[i]=5 length=1

a[i]=4 length=2

a[i]=3 length=3

a[i]=2 length=4

a[i]=1 length=5

a[i]=2 length=1

[5, 4, 3, 2, 1, 1]

max length=5

进一步相似题目：

【dfs && 记忆化搜索】329. 矩阵中的最长递增路径