卜若的代码笔记-算法系列-第3个算法案例分析：斐波那契最长动态规划算法

题目2：Fibonacci Subsequence

A sequence of integer numbers a1 , a2 , ..., an is called a Fibonacci sequence if ai = ai-2+ai-1 for all i=3,4,...,n.

Given a sequence of integer numbers c1 , c2 , ..., cm you have to find its longest Fibonacci subsequence.

Input

There are several test cases in the input. The first line of each case contains m (1 <= m <= 3,000). Next line contains m integer numbers not exceeding 109 by their absolute value.

There is a new line between each case.

Output

On the first line of each case print the maximal length of the Fibonacci subsequence of the given sequence. On the second line print the subsequence itself.
There is a new line between each case.

Sample Input

10

1 1 3 -1 2 0 5 -1 -1 8

Sample Output

5

1 -1 0 -1 -1

 

                          

代码：(哎，针对这些东西都是只可意会不可言传，说不清楚，真的)

package com.company;

import java.util.HashMap;
import java.util.Stack;

public class FBNQDp {

    public int[][] dp;

    public int[] originData;

    public int len;
    public int Ai;
    public int Aj;
    public HashMap<Integer,Integer> hashMap;

    public int max(int v1,int v2){

        if (v1>v2)
            return v1;

        return v2;
    }
    public void initData(int[] originData ){
        this.len = originData.length;
        dp = new int[len][len];
        hashMap = new HashMap<>();
        for (int i =0;i<len;i++){
            for(int j =0;j<len;j++){
                dp[i][j] = 2;
            }
        }
        for (int i =0;i<len;i++){

            if (!hashMap.containsKey(originData[i])){

                hashMap.put(originData[i],i);
            }


        }

        this.originData = originData;


    }
    public int getMax(){
        int max = dp[0][0];
        for (int i =0;i<len;i++){
            for (int j =0;j<len;j++){
               // System.out.println(dp[i][j]);
                if (max<dp[i][j]){
                    max = dp[i][j];
                    Ai = originData[i];
                    Aj = originData[j];
                }

            }
        }

        return max;
    }

    public void dynamicPlaning(){
        for (int i =0;i<len;i++){
            for (int j = i+1;j<len;j++){
                int f1 = originData[i];
                int f2 = originData[j];
                int kValue = f2 - f1;
                if (hashMap.containsKey(kValue)){
                    int k = hashMap.get(kValue);
                    dp[i][j] =max(dp[i][j],dp[k][i]+1);
                }
            }
            hashMap.put(originData[i],i);
        }
    }

    public static void main(String[] arg){
        FBNQDp dp = new FBNQDp();
        int[] ori = new int[]{1,1,3,-1,2,0,5,-1,-1,8};
        dp.initData(ori);
        dp.dynamicPlaning();

        int max = dp.getMax();
        Stack answerStack = new Stack();
        answerStack.push(dp.Aj);
        answerStack.push(dp.Ai);
        for (int i =2;i<max;i++){

            int sub = dp.Aj - dp.Ai;
            dp.Aj = dp.Ai;
            dp.Ai =sub;
            answerStack.push(sub);

        }
        String fibValue = "";
        while (!answerStack.isEmpty()){
            fibValue+= answerStack.pop() +" ";

        }
        System.out.println(fibValue);


        System.out.println(max);


    }

}