Problem statement:

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Solution Memo

public int lengthOfLIS(int[] nums) {
    Integer[][] dp = new Integer[nums.length + 1][nums.length + 1];
    return lengthOfLISRec(nums, 0, -1, dp);
}

int lengthOfLISRec(int[] nums, int curr, int prev, Integer[][] dp) {
    if (curr >= nums.length) {
        return 0;
    }

    if (dp[curr + 1][prev + 1] == null) {
        int c1 = 0;
        if (prev == -1 || nums[curr] > nums[prev]) {
            c1 = 1 + lengthOfLISRec(nums, curr + 1, curr, dp);
        }
        int c2 = lengthOfLISRec(nums, curr + 1, prev, dp);
        dp[curr + 1][prev + 1] = Math.max(c1, c2);
    }
    return dp[curr + 1][prev + 1];
}

Solution Bottom UP

public int lengthOfLISLenBUMy(int[] nums) {
    int[] dp = new int[nums.length];
    Arrays.fill(dp, 1);
    int max = 1;
    for (int i = 1; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(1 + dp[j], dp[j]);
            }
            max = Math.max(max, dp[i]);
        }
    }
    return max;
}

Time complexity:

O(N^2)

Space complexity:

O(N)

Approach:

for recursive: init currentIndex = 0 and prev = -1 and either move curr + 1 and assign prev to current or just move current and keep prev; for bottomUp: one-dim array i = 1 ++ and j = 0 up to i; if num[i] > num[j] → dp[i] = max(dp[j] + 1, dp[i]); return max