中国平安的编程

动态规划：最长递增子序列的变形，

考试时没写完，考试后10分钟内才发现left<arr[j]写成=的错误，没招了，

n>=3

输入1，2，3，4，5，6，7，8严格递增

返回最长斐波那契子序列长度为5

没有返回0

import java.util.*;

class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.nextLine();
        String[] aa = a.split(",");
        int len = aa.length;
        int[] arr = new int[len];
        HashMap<Integer,Integer> ma = new HashMap<>();
        for(int i =0;i<len;i++){
            arr[i] = Integer.parseInt(aa[i]);
            ma.put(arr[i],i);
        }
        int[] dp = new int[len];
        dp[0] = 1;
        dp[1]=2;
        if(arr[2]==arr[1]+arr[0]){
            dp[2] = 3;
        }
        int max = 2;
        for(int i = 3;i<=len-1;i++){
            int cur = arr[i];
            System.out.println(i+":");
            for(int j=i-1;j>=2;j--){//中间的那一位
                int left = cur - arr[j];
                if(left<arr[j]&&ma.containsKey(left)){
                    //进行更新值
                    int idx = ma.get(left);
                    dp[i] = Math.max(dp[i],2+dp[idx]);
                    System.out.println(arr[j]+" "+left+" "+dp[i]);
                }
            }
//            System.out.println(i+"-"+arr[i]+":"+dp[i]);
            max = Math.max(max,dp[i]);
        }
        if(max<=2){
            System.out.println("0");
        }else{
            System.out.println(max);
        }
    }
}