673. Number of Longest Increasing Subsequence

Description

Here

Intuition

If we scan from the left to right, we need update from some data from [min, nums[i]], so we need something like Binary Index Tree or Segement Tree.

Another interesting point is that since we are using a very large range, if we use a normal Segment Tree, the space will be amazingly shit. Generally, we have 2 ways to solve this issue.

• Coordination Compression
• Lazy Propagation

Solution

First, we should create a class called Node, which represents the information from [min, nums[i]]. For example, the valin Node{min = 1, max = 7} indicates the max LIS length and count, ranging from the min value in the array, to [1, 7]

  private static final class Node {

    private final int min, max;
    private Node left, right;
    private Value val = new Value(0, 1);

    public Node(int min, int max) {
      this.min = min;
      this.max = max;
    }

    private int getMid() {
      return (max - min) / 2 + min;
    }

    /**
     * One way to do lazy propagation
     *
     * @return
     */
    public Node getLeft() {
      if (left == null) {
        left = new Node(min, getMid());
      }
      return left;
    }

    public Node getRight() {
      if (right == null) {
        right = new Node(getMid() + 1, max);
      }
      return right;
    }
  }

  private static final class Value {
    private final int length;
    private final int count;

    public Value(int length, int count) {
      this.length = length;
      this.count = count;
    }

    public Value(Value val) {
      this.length = val.length;
      this.count = val.count;
    }

    @Override
    public String toString() {
      return "Value{" +
          "length=" + length +
          ", count=" + count +
          '}';
    }
  }

Then, we only need to implement the update and query