Longest Increasing Subsequence

Today we’re going to look at Longest Increasing Subsequence and we’re going to focus on providing the O(n²) solution. While there is a faster O(nlog(n)) solution, the O(n²) solution is more initiative and provides more learning for future problems you may see on interviews.

To understand the intuition behind the problem, you need to make note of a few things. Consider the input nums=[6, 7, -2, 0, 8, 2, 3]

1. The longest increasing subsequence in 0...i is one plus the lonest increasing subsequence that exists for all valid sequences possible in the range 0...j where j<i and the last number of the sequence is less than nums[i].

In our example, the longest sequence at i=4 (nums[4] = 8) is the longest sequence that exists in the subset of nums 0...i-1 ([6, 7, -2, 0]) and where the last number in the sequence is less than 8. In this case, the longest sequence is [6, 7].

2. We can always add a new number to the end of a sequence if that number is greater than the last number of the sequence.

Thus, to get the longest subsequence for a input nums[0…i], we need take the longest subsequence that can be generated for the subsets:
nums[0, 1]
nums[0, 2]
…
nums[0, i-1]

but we can only consider the subsets where the last number is less than nums[i]. If it was a higher number, the subsequence would not be strictly increasing.

And by fact #1, once we found a subsequence nums[0, j] that gives us the longest subsequence, we can make a even longer subsequence by adding nums[i] to the end.

Let’s denote f(nums, i) = the longest subsequence length for nums from index 0 to i. To run the algorithm above, we are going to be executing f(nums, i) for many times with the same value of i and ii) we’re also breaking the problem f(nums, i) to subproblems max (f(nums, 1), f(nums, 2)…f(nums, i-1)) considering the optimal solution to each subproblems in our final problem. This sounds like dynamic programing.

DP Table

The DP table is of length 0 to nums.length, where each position i keeps track of the longest subsequence length using a subset of nums, nums[0, i].

Tabulation

	public int lengthOfLIS(int[] nums) {

		int[] memo = new int[nums.length];
		Arrays.fill(memo, 1);

		if (nums.length == 1) {
			return 1;
		}

		for (int i = 1; i < nums.length; i++) {

			for (int j = 0; j < i; j++) {
				if (nums[j]  memo[i]) {
					memo[i] = memo[j] + 1;
				}
			}

		}
	
		Arrays.sort(memo);
		return memo[memo.length-1];
	}

Conclusion

I’ve decided the keep the source code fairly verbose in order to maintain readability. While there are more efficient methods (to the O(n²) solution provided above, I believe it’s better (in terms of interview preparation) to write readable solutions in order to form key takeaways then to confuse people wile saving a small amount of memory.

As mentioned above, there is a more efficient O(nlong) solution, but we won’t cover that today.