Google – Arbitrary Tree Longest Consecutive Path

Google – Arbitrary Tree Longest Consecutive Path
有两种题型：
1 只算从上到下，像leetcode298 Binary Tree Longest Consecutive Sequence
2 任意path
注意这里tree是任何的tree，不是binary tree.
[Solution]
第一题就是简单的dfs，简单到面试碰到原题还写出bug。他妈的…
第二题倒是非常复杂，对于每个node，要求4条最长路径:
1. 最长的递增path
2. 最长的递减path
3. 从左到右最长的path
4. 从右到左最长的path
递归return的是1，2两条，可以Wrap一个Pair class，也可以用HashMap.

  public int maxSumSubmatrix(int[][] matrix, int k) {

    if (matrix == null || matrix.length == 0) {

      return 0;

    }

    int m = matrix.length;

    int n = matrix[0].length;

    int result = Integer.MIN_VALUE;

    for (int i = 0; i < n; i++) {

      int r = i;

      int[] local = new int[m];

      while (r < n) {

        for (int x = 0; x < m; x++) {

          local[x] += matrix[x][r];

        }

        int localResult = maxSubArray(local, k);

        result = Math.max(result, localResult);

        r++;

      }

    }

    return result;

  }

  // maximum subarray less than k

  // can not use two pointer, [2, -7, 6, -1], k = 0

  // TreeSet, find ceiling, O(nlogn)

  private int maxSubArray(int[] nums, int k) {

    int result = Integer.MIN_VALUE;

    TreeSet<Integer> tSet = new TreeSet<>();

    int[] sums = new int[nums.length];

    sums[0] = nums[0];

    tSet.add(sums[0]);

    if (sums[0] <= k) {

      result = Math.max(result, sums[0]);

    }

    for (int i = 1; i < nums.length; i++) {

      sums[i] = sums[i - 1] + nums[i];

      if (sums[i] <= k) {

        result = Math.max(result, sums[i]);

      }

      Integer ceil = tSet.ceiling(sums[i] - k);

      if (ceil != null) {

        result = Math.max(result, sums[i] - ceil);

      }

      tSet.add(sums[i]);

    }

    return result;

  }

  // TreeSet find floor

  private int maxSubArray2(int[] nums, int k) {

    int n = nums.length;

    int result = Integer.MIN_VALUE;

    TreeSet<Integer> tSet = new TreeSet<>();

    int[] sums = new int[n];

    int sum = 0;

    for (int i = 0; i < n; i++) {

      sum += nums[i];

    }

    for (int i = n - 1; i >= 0; i--) {

      sums[i] = sum;

      if (sums[i] <= k) {

        result = Math.max(result, sums[i]);

      }

      if (i != n - 1) {

        Integer floor = tSet.floor(sums[i] + k);

        if (floor != null) {

          result = Math.max(result, floor - sums[i]);

        }

      }

      sum -= nums[i];

      tSet.add(sums[i]);

    }

    return result;

  }

Read full article from Google – Arbitrary Tree Longest Consecutive Path