找出数组中最大递增子数组，找出二叉树节点的最长距离，JS怎么写

Question

今天面试遇到的两个问题，用JS写出：
1、找出二叉树节点的最长距离
2、找出数组中的最长递增序列

想了半天是在没想出来，求大佬们赐教（代码来点注释可好，算法渣很无力呀。。。）

Answer 1

希望你去看一下动态规划算法...

Answer 2

这2题目稍微百度一下都有，而且带注释。

Answer 3

这样的问题还需要问……？搜索一下铺天盖地！

http://www.cnblogs.com/miloyi...
http://www.cnblogs.com/whyand...

Answer 4

最长自增序列 https://github.com/hanzichi/l...

代码：https://github.com/hanzichi/l...

Answer 5

其实细想一下题目并不复杂，二叉树计算一下每个节点左边最大深度和右边最大深度之和，最后选择最大的就可以。
数组题计算每个节点之前最长递增序列，再加上本节点，就是包括当前节点之前的最长子序列，记住长度和前一个节点的下标，从第一个节点开始遍历到最后一个，选择计算出的所有的节点最大长度，就是最长的了。
方法比代码重要

Answer 6

我写过最长递增子序列,仅作参考，二叉树问题应该类似，都是动态规划问题，可以看看左程云的《程序员代码面试指南》

// 给定数组arr，返回arr的最长递增子序列的长度，比如arr=[2,1,5,3,6,4,8,9,7]，最长递增子序列为[1,3,4,8,9]返回其长度为5.
// dp[i]表示以必须arr[i]这个数结束的情况下产生的最大递增子序列的长度。对于第一个数来说，很明显dp[0]为1，当我们计算dp[i]的时候，
// 我们去考察i位置之前的所有位置，找到i位置之前所有比arr[i]小的位置中最大的那个值，记为dp[j](0=<j<i),
// dp[j]代表以arr[j]结尾的最长递增序列，而dp[j]又是之前计算过的最大的那个值，
// 则dp[i]=dp[j]+1.计算完dp之后，我们找出dp中的最大值，即为这个串的最长递增序列
let arr=[2,1,5,3,6,4,8,9,7];
function search(arr) {
    let temp=[1];
    for(let i=1;i<arr.length;i++){
        let temp_arr=arr.slice(0,i);
        let flag=[];
        for(let j=0;j<temp_arr.length;j++){
            if(arr[j]<arr[i]){
                flag.push(temp[j])
            }
        }
        if(flag.length===0){
            temp.push(1)
        }else{
            temp.push(Math.max(...flag)+1)
        }
    }
    return Math.max(...temp)
}