# 20200219

Input: [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Input: [-2, 1, 2, 3, -9, 1, 10]
Output: 11

-min ~ max

[-2, 1, -3, 4, -1, 2, 1, -5, 4]
[-2, 1, -2, 4, 3, 5, 6, 1, 5]
6

public int maxSub(int[] input) {
    int max = input[0];
    for (int i = 1; i < input.length; i++) {
        if (input[i] < input[i] + input[i - 1]) {
            input[i] = input[i] + input[i - 1];
        }
        
        max = Math.max(max, input[i]);
    }
    return max;
}

root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 7

3(n)
/ \
5(5) 1(n)
/ \ / \
6 2 0(n)8(n)
/ \
7 4

//Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public TreeNode lowestAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root.val == p.val || root.val == q.val) {
        return root
    } else if (lowestAncestor(root.left, p, q) == null) 
        return right;
    } else if ( lowestAncestor(root.right, p, q) == null) {
        return left;
    } else {
        return root;
    }
}

Input: [1, 0, 3, 0, 4, 2]
Output: [1, 3, 4, 2, 0, 0]

fast 1
slow 1
arr = [1, 0, 3, 0, 4, 2]

if (arr[fast] != 0) {
int temp = 1
arr[fast] = arr[slow]
arr[slow] = temp
slow++;
}

fast++

[1, 0, 3, 0, 4, 2]

[1, 3, 0, 0, 4, 2]
f
s
[1, 3, 4, 0, 0, 2]

[1, 3, 4, 2, 0, 0]

public void moveZeroes(int[] nums) {
    int slow = 0;
    for (int fast = 0; fast < nums.length; fast++) {
    if (arr[fast] != 0) {
        int temp = arr[fast];
        arr[fast] = arr[slow];
        arr[slow] = temp;
        slow++;
    }
}