Daily Archives: June 21, 2015

Maximum Product Subarray

Posted on by
Reply

Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example

For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6.

Solution: One Pass O(n) time.

So for each index i, max(i) = the maximum product ending at i, so we have

max(i) = max(max(i-1)*nums[i], nums[i]) //nums[i]>=0

since you can either append from the previous one, or just start a new contiguous subarray.

Be careful on negative nums, if nums[i] < 0, the equation now becomes:

max(i) = max(min(i-1)*nums[i], nums[i]) //nums[i]<0

public int maxProduct(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int maxProduct = Integer.MIN_VALUE;
    int preMax = 1;
    int preMin = 1;
    for (int i = 0; i < nums.length; i++) {
        int max, min;
        if (nums[i] >= 0) {
            max = Math.max(preMax * nums[i], nums[i]);
            min = Math.min(preMin * nums[i], nums[i]);
        } else {
            max = Math.max(preMin * nums[i], nums[i]);
            min = Math.min(preMax * nums[i], nums[i]);
        }
        maxProduct = Math.max(maxProduct, max);
        preMax = max;
        preMin = min;
    }
    return maxProduct;
}
FacebookTwitterGoogle+Share

Segment Tree

Posted on by
Reply

Segment Tree(线段树)

性质：

  1. 二叉树
  2. 线段树的每个节点表示的是一段区间和最大值（或最小值）
  3. 节点的左子树 = 父亲区间分裂后的左区间

节点的右子树 = 父亲区间分裂后的右区间

查询：O(logN) 时间

  1. 查询的区间 和 线段树节点表示的区间 相等 -》直接返回节点的最大值
  2. 查询的区间 被 线段树节点表示的区间 包含 -》递归向下搜索左右子树
  3. 查询的区间 和 线段树节点表示的区间 不相交 -》停止搜索子树
  4. 查询的区间 和 线段树节点表示的区间 相交不相等 -》分裂查找左右子树 eg.max[1,3] = max([1,1], [2,3])

建立：O(n) 时间

  1. 自上而下递归分裂
  2. 自下而上回溯更新

Segment Tree Query

For an integer array (index from 0 to n-1, where n is the size of this array), in the corresponding SegmentTree, each node stores an extra attribute max to denote the maximum number in the interval of the array (index from start to end).

Design a query method with three parameters root, start and end, find the maximum number in the interval [start, end] by the given root of segment tree.

Example

For array [1, 4, 2, 3], the corresponding Segment Tree is:

<code>                  [0, 3, max=4]
                 /             \
          [0,1,max=4]        [2,3,max=3]
          /         \        /         \
   [0,0,max=1] [1,1,max=4] [2,2,max=2], [3,3,max=3]
</code>

query(root, 1, 1), return 4

query(root, 1, 2), return 4

query(root, 2, 3), return 3

query(root, 0, 2), return 4

Note

It is much easier to understand this problem if you finished Segment Tree Build first.

public int query(SegmentTreeNode root, int start, int end) {
    if (root == null) {
        return -1;
    }
    if (root.start == start && root.end == end) {
        return root.max;
    }
    int mid = root.start + (root.end - root.start) / 2;
    int leftMax = Integer.MIN_VALUE;
    int rightMax = Integer.MIN_VALUE;
    if (start <= mid) {
        if (end <= mid) {
            leftMax = query(root.left, start, end);
        } else {
            leftMax = query(root.left, start, mid);
        }
    }
    if (end > mid) {
        if (start >= mid) {
            rightMax = query(root.right, start, end);
        } else {
            rightMax = query(root.right, mid + 1, end);
        }
    }
    return Math.max(leftMax, rightMax);
}

Segment Tree Query II

For an array, we can build a SegmentTree for it, each node stores an extra attributecount to denote the number of elements in the the array which value is between interval start and end. (The array may not fully filled by elements)

Design a query method with three parameters root, start and end, find the number of elements in the in array’s interval [start, end] by the given root of value SegmentTree.

Example

For array [0, 2, 3], the corresponding value Segment Tree is:

<code>                     [0, 3, count=3]
                     /             \
          [0,1,count=1]             [2,3,count=2]
          /         \               /            \
   [0,0,count=1] [1,1,count=0] [2,2,count=1], [3,3,count=1]
</code>

query(1, 1), return 0

query(1, 2), return 1

query(2, 3), return 2

query(0, 2), return 2

Note

It is much easier to understand this problem if you finished Segment Tree Build and Segment Tree Query first.

public int query(SegmentTreeNode root, int start, int end) {
    if (root == null || start > root.end || end < root.start) {
        return 0;
    }
    if (root.start == start && root.end == end) {
        return root.count;
    }
    int mid = root.start + (root.end - root.start) / 2;
    int leftCount = 0, rightCount = 0;
    if (start <= mid) {
        if (end <= mid) {
            leftCount = query(root.left, Math.max(start, root.start), end);
        } else {
            leftCount = query(root.left, Math.max(start, root.start), mid);
        }
    }
    if (end >= mid) {
        if (start >= mid + 1) {
            rightCount = query(root.right, start, Math.min(end, root.end));
        } else {
            rightCount = query(root.right, mid + 1, Math.min(end, root.end));
        }
    }
    return leftCount + rightCount;
}

Segment Tree Modify

For a Maximum Segment Tree, which each node has an extra value max to store the maximum value in this node’s interval.

Implement a modify function with three parameter root, index and value to change the node’s value with [start, end] = [index, index] to the new given value. Make sure after this change, every node in segment tree still has the max attribute with the correct value.

Example

For segment tree:

<code>                      [1, 4, max=3]
                    /                \
        [1, 2, max=2]                [3, 4, max=3]
       /              \             /             \
[1, 1, max=2], [2, 2, max=1], [3, 3, max=0], [4, 4, max=3]
</code>

if call modify(root, 2, 4), we can get:

<code>                      [1, 4, max=4]
                    /                \
        [1, 2, max=4]                [3, 4, max=3]
       /              \             /             \
[1, 1, max=2], [2, 2, max=4], [3, 3, max=0], [4, 4, max=3]
</code>

or call modify(root, 4, 0), we can get:

<code>                      [1, 4, max=2]
                    /                \
        [1, 2, max=2]                [3, 4, max=0]
       /              \             /             \
[1, 1, max=2], [2, 2, max=1], [3, 3, max=0], [4, 4, max=0]
</code>
Note

We suggest you finish problem Segment Tree Build and Segment Tree Query first.

Challenge

Do it in O(h) time, h is the height of the segment tree.