Thinking process I -- DP

The sequence doesn't need to be continuous.

• which makes the question more difficult.

Then, where to start and where to end?

• try to find the state that is independent from the next state
• and the final result rely on the previous states

What is the longest increasing subsequence so far?

• which means, nums[i] is the last number

Then, how states connect to each other?

• for each state j < i, how to pass from it to state i?
• This is possible when nums[j] < nums[i]

Mistakes

increasing!

• no equal!

State function

if nums[j] <= nums[i]

dp[i] = Math.max(dp[i], dp[j] + 1)

Time Complexity

O(n^2)

public class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null) return -1;

        int[] dp = new int[nums.length];
        int ans = 0;

        for (int i = 0; i < nums.length; ++i) {
            dp[i] = 1;
        }

        for (int i = 0; i < nums.length; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            ans = Math.max(dp[i], ans);
        }

        return ans;
    }
}

Thinking Process II -- Binary Search

There are two possible ways? Which one is feasible?

• iterate over the input array and find something using binary search
• search by the range, and iterate over the input array

If it's the first one,

• find the first element that is larger than nums[i] in dp array
• initial values are Integer.MAX_VALUE

If it's the second one,

• can't achieve it using linear time

So, following the first thought, but thinking about this corner cases

• 1 6 8 5 9
• the sequence in dp would be

1
1 6
1 6 8
1 5 8
1 5 8 9

• 1 5 8 9 is not the answer, 1 6 8 9 is.
• But this doesn't matter, because if we use a smaller number on the right replace one bigger number on the left, the len won' change at all.

Mistakes

the length of minLast array?

the initial values of each number in minLast?

after the loop in binary search function, return left or right?

• [2, 2] => 1

Time Complexity

O (n log n)

public class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null) return -1;

        int[] minLast = new int[nums.length];//the smallest number that is bigger than current

        for (int i = 0; i < minLast.length; ++i) {
            minLast[i] = Integer.MAX_VALUE;
        }

        for (int i = 0; i < nums.length; ++i) {
            int index = find(minLast, nums[i]);
            minLast[index] = nums[i];
        }

        for (int i = minLast.length - 1; i >= 0; --i) {
            if (minLast[i] != Integer.MAX_VALUE) return i + 1;
        }

        return 0;

    }

    private int find(int[] minLast, int num) {
        int l = 0; 
        int r = minLast.length - 1;

        while (l + 1 < r) {
            int mid = l + (r - l) / 2;
            if (minLast[mid] > num) {
                r = mid;
            } else {
                l = mid;
            }
        }

        if (minLast[l] >= num) {
            return l;
        } 

        return r;
    }
}