## Monday, August 8, 2016

### Google – Arbitrary Tree Longest Consecutive Path

Google – Arbitrary Tree Longest Consecutive Path

1 只算从上到下，像leetcode298 Binary Tree Longest Consecutive Sequence
2 任意path

[Solution]

1. 最长的递增path
2. 最长的递减path
3. 从左到右最长的path
4. 从右到左最长的path

`  ``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;`
`  ``}`