动态规划-1：穷举遍历-＞map缓存-＞取消递归

import java.util.HashMap;
import java.util.Map;

public class DynamicProgrammingAlgorithm {

    public static void main(String[] args) {
        //比如 要求一个数组的最长递增子序列的长度
        //比如是[1,4,2,5,3],那么[1,2,5],或者[1,2,3]都是最长递增子序列，所以应该返回3
        //如何用算法实现，最简单的方法是暴力枚举
        int[] arr = {1,4,2,5,3};
        int largestAscendingSubArrLength = getLargestAscendingSubArrLength(arr);
        System.out.println(largestAscendingSubArrLength);

        int[] arr2 = {958,95,812,650,443,412,872,921,975,201,576,548,
                257,694,53,797,640,424,556,955,806,807,467,45,270,565,
                778,662,537,435,167,867,971,108,810,838,401,809,803,702,
                836,654,491,14,729,890,684,293,732,892,326,664,815,566,
                434,592,877,657,611,795,474,408,266,975,589,316,681,763,
                115,941,328,311,108,263,822,447,600,914,326,478,386,117,928,
                978,383,110,392,373,67,335,64,62,956,950,778,363,13,524,686,
                411,654,346,345,768,505,822,556,350,353,706,689,844,500,488,614,
                587,540,437,886,273,561,798,341,149,817,878,418,134,99,398,731};


        long start = System.currentTimeMillis();
        System.out.println(getLargestAscendingSubArrLength(arr2));
        System.out.println("用了"+(System.currentTimeMillis()-start)+ "毫秒");

        System.out.println("===================================");
        System.out.println(getSubArrLengthFromGivingStartAdvanced(arr));
        System.out.println(getSubArrLengthFromGivingStartAdvanced(arr2));
    }

    public static int getLargestAscendingSubArrLength(int[] arr){

        /**
         * key:表示从哪个索引index开始查找递增子序列
         * value:表示从索引key开始的最长递增子序列为value个
         */
        Map<Integer,Integer> map = new HashMap<>();

        //我从1开始,先找所有以1开头的子序列；然后找4；以此类推
        int large = 0;
        for (int i = 0; i < arr.length; i++) {
            int tmpLarge = getSubArrLengthFromGivingStart(arr, i);
            if (tmpLarge > large){
                large = tmpLarge;
            }
        }
        return large;
    }

    /**
     * 返回数组arr从startIndex开始的最长递增子序列的长度
     * @param arr
     * @param startIndex
     * @return
     * //比如是arr = [1,4,2,5,3] startIndex=0
     */
    public static int getSubArrLengthFromGivingStart(int[] arr,int startIndex){
        int maxLen = 1;

        if (startIndex < arr.length-1){
            for (int i = startIndex + 1; i < arr.length; i++) {
                if (arr[i] > arr[startIndex]){
                    int tmp = getSubArrLengthFromGivingStart(arr,i)+1;
                    maxLen = tmp>maxLen?tmp:maxLen;
                }
            }
        }
        //如果传入startIndex = arr.length-1,也即从最后一个元素开始找，显然是1
        return maxLen;
    }

    /**
     * 上述getSubArrLengthFromGivingStart最大的问题在于存在大量的重复计算
     * 比如startIndex=3,也即从元素5开始的子序列，我们计算1,5,3时计算过，计算2,5,3时也要计算
     * 优化方案，把计算过的值存起来，直接取，避免重复计算
     * @param arr
     * @param startIndex
     * @return
     */
    public static int getSubArrLengthFromGivingStart(int[] arr,int startIndex,Map<Integer,Integer> map){

        Integer value = map.get(startIndex);
        if (value != null){
            return value;
        }

        int maxLen = 1;

        if (startIndex < arr.length-1){
            for (int i = startIndex + 1; i < arr.length; i++) {
                if (arr[i] > arr[startIndex]){
                    int tmp = getSubArrLengthFromGivingStart(arr,i)+1;
                    maxLen = tmp>maxLen?tmp:maxLen;
                }
            }
        }
        //如果传入startIndex = arr.length-1,也即从最后一个元素开始找，显然是1
        //放入缓存中
        map.put(startIndex,maxLen);
        return maxLen;
    }

    /**
     * 改进为非递归 
     * 时间复杂度o(n^2),比一开始的指数级好太多了
     * @param arr
     * @return
     */
    public static int getSubArrLengthFromGivingStartAdvanced(int[] arr){

        Map<Integer,Integer> map = new HashMap<>();

        for (int i = arr.length-1; i >= 0; i--) {//每次循环计算从序号i开始的最长递增子序列的长度
            int maxLen = 1;
            //如果i是最后一个元素，则显然最长递增子序列的长度就是1。continue结束本次循环
            if (i == arr.length-1){
                map.put(i,maxLen);
                continue;
            }

            for (int j = i+1; j < arr.length; j++) {
                if (arr[i] < arr[j] ){
                    int tmp = map.get(j)+1;
                    maxLen = tmp > maxLen? tmp:maxLen;
                }
            }
            map.put(i,maxLen);
        }

        //上面算出了从每个index触发开头的最长递增子序列的长度，这里选其中最大的返回
        int max = 1;
        for (int i = 0; i < arr.length; i++) {
            Integer tmp = map.get(i);
            max = tmp>max?tmp:max;
        }
        return max;
    }

}