For array [10, 9, 2, 5, 3, 7, 101, 18], one LIS is [2, 3, 7, 18] with length 4. Another is [2, 5, 7, 101] and many others, but the largest possible length possible is 4. That's the goal.

If, we at each position, we only care about the longest increasing subsequence ending at that position, we can end up in a tabulation, which we'll get to eventually. It is an obvious pattern at this point, especially after the three previous problems solved, so just for formality's sake let's get into the Recursion and Memoisation steps too.

Recursion

int lisRecursive(vector<int>& nums, int i, int prevIndex) {
    // Base case: reached end of array
    if (i == nums.size()) return 0;
    
    // Option 1: Skip current element
    int skip = lisRecursive(nums, i + 1, prevIndex);
    
    // Option 2: Take current element (if valid)
    int take = 0;
    if (prevIndex == -1 || nums[i] > nums[prevIndex]) {
        take = 1 + lisRecursive(nums, i + 1, i);
    }
    
    return max(skip, take);
}

Refer to the table of all time and space complexity of all scenarios at end of article.

Memoised

int lisMemoHelper(vector<int>& nums, int i, int prevIndex, vector<vector<int>>& memo) {
    if (i == nums.size()) return 0;
    
    if (memo[i][prevIndex + 1] != -1) {
        return memo[i][prevIndex + 1];
    }
    
    // ... rest of logic
}

Bottom Up 2D Tabulation

int lisBottomUp2D(vector<int>& nums) {
    int n = nums.size();
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
    
    for (int i = n - 1; i >= 0; i--) {
        for (int prevIndex = i - 1; prevIndex >= -1; prevIndex--) {
            // ... logic
        }
    }
}

But we can do better than this!

Bottom Up 1D Version

For position i:
- Look at all positions j where j < i
- If nums[j] < nums[i]:
    - We can extend the sequence ending at j
    - New length would be: (best sequence ending at j) + 1
- Pick the maximum among all such extensions
- If no valid j exists, sequence length is just 1

Simple example:

Array: [2, 5, 3, 7]
At position 3 (value = 7):

Look back: positions 0, 1, 2 have values 2, 5, 3
All are < 7, so we can extend any of them
Best sequence ending at pos 0: length 1
Best sequence ending at pos 1: length 2 (because 2→5)
Best sequence ending at pos 2: length 2 (because 2→3)
Pick the best: length 2, add myself: 2 + 1 = 3
So dp[3] = 3 (sequence: 2→5→7 or 2→3→7)

int lisBottomUp1D(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1);
    
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) 
                dp[i] = max(dp[i], dp[j] + 1);
        }
    }
}

Dry run:

Array: [10, 9, 2, 5, 3, 7, 101, 18]
Initial state: dp = [1, 1, 1, 1, 1, 1, 1, 1]
i = 1 (nums[1] = 9):

j = 0: nums[0] = 10, 10 ≮ 9, skip
dp[1] remains 1

i = 2 (nums[2] = 2):

j = 0: nums[0] = 10, 10 ≮ 2, skip
j = 1: nums[1] = 9, 9 ≮ 2, skip
dp[2] remains 1

i = 3 (nums[3] = 5):

j = 0: nums[0] = 10, 10 ≮ 5, skip
j = 1: nums[1] = 9, 9 ≮ 5, skip
j = 2: nums[2] = 2, 2 < 5 ✓, dp[3] = max(1, dp[2] + 1) = max(1, 2) = 2
dp[3] = 2

i = 4 (nums[4] = 3):

j = 0,1: skip (10,9 ≮ 3)
j = 2: nums[2] = 2, 2 < 3 ✓, dp[4] = max(1, dp[2] + 1) = 2
j = 3: nums[3] = 5, 5 ≮ 3, skip
dp[4] = 2

i = 5 (nums[5] = 7):

j = 2: nums[2] = 2, 2 < 7 ✓, dp[5] = max(1, 1 + 1) = 2
j = 3: nums[3] = 5, 5 < 7 ✓, dp[5] = max(2, 2 + 1) = 3
j = 4: nums[4] = 3, 3 < 7 ✓, dp[5] = max(3, 2 + 1) = 3
dp[5] = 3

i = 6 (nums[6] = 101):

All previous elements are < 101
Best is dp[5] = 3, so dp[6] = 3 + 1 = 4

i = 7 (nums[7] = 18):

j = 2: 2 < 18, dp[7] = max(1, 1 + 1) = 2
j = 3: 5 < 18, dp[7] = max(2, 2 + 1) = 3
j = 4: 3 < 18, dp[7] = max(3, 2 + 1) = 3
j = 5: 7 < 18, dp[7] = max(3, 3 + 1) = 4
j = 6: 101 ≮ 18, skip
dp[7] = 4

Final dp: [1, 1, 1, 2, 2, 3, 4, 4]
Maximum value = 4, so LIS length = 4.

DP is about using brains. By following rules, you can always end up in tabulation stage, but from after it is all about coming up with other ways to optimise. What if even this ain't the best we can do? Since it is 1D, can't we also have a search going on?

Binary Search Version

int lisOptimal(vector<int>& nums) {
    vector<int> tails;
    
    for (int num : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), num);
        if (it == tails.end()) {
            tails.push_back(num);
        } else {
            *it = num;
        }
    }
    
    return tails.size();
}

lower_bound(tails, num) finds the first position where num can be inserted to keep the array sorted.
If num is larger than all elements: returns end() (append)
If num fits somewhere in middle: returns iterator to that position (replace)

When we replace tails[i] = num, we're saying: "I found a better (smaller) ending element for LIS of length i+1". This doesn't destroy any existing LIS, rather gives us a better foundation for building longer ones.

Dry Run:

Array: [10, 9, 2, 5, 3, 7, 101, 18]
Initial: tails = []

num = 10:
- tails is empty, so append 10
- tails = [10]
- Meaning: "Best LIS of length 1 ends with 10"

num = 9:
- lower_bound(tails, 9) finds position 0 (9 < 10)
- Replace tails[0] = 9
- tails = [9]
- Meaning: "Found better LIS of length 1 ending with 9"

num = 2:
- lower_bound(tails, 2) finds position 0 (2 < 9)
- Replace tails[0] = 2
- tails = [2]
- Meaning: "Even better LIS of length 1 ending with 2"

num = 5:
- lower_bound(tails, 5) finds end (5 > 2)
- Append 5
- tails = [2, 5]
- Meaning: "Found LIS of length 2: can follow 2 with 5"

num = 3:
- lower_bound(tails, 3) finds position 1 (3 > 2 but 3 < 5)
- Replace tails[1] = 3
- tails = [2, 3]
- Meaning: "Better LIS of length 2 ending with 3 instead of 5"

num = 7:
- lower_bound(tails, 7) finds end (7 > 3)
- Append 7
- tails = [2, 3, 7]
- Meaning: "Found LIS of length 3"

num = 101:
- lower_bound(tails, 101) finds end
- Append 101
- tails = [2, 3, 7, 101]
- Meaning: "Found LIS of length 4"

num = 18:
- lower_bound(tails, 18) finds position 3 (18 > 7 but 18 < 101)
- Replace tails[3] = 18
- tails = [2, 3, 7, 18]
- Meaning: "Better LIS of length 4 ending with 18"

Final: tails.size() = 4

Table of Complexities:

Bye!