Dynamic Programming (Part 4): Longest Increasing Subsequence (LIS)

Dynamic Programming
Fenwick Tree (Binary Indexed Tree)

Dynamic Programming

We can define as the maximum length of increasing subsequence ending at index (a common pattern for the array). Then, we can write the state transition equation as

Finally, the result of this problem is , and the code is as follows:

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

The time complexity of this solution is .

Fenwick Tree (Binary Indexed Tree)

The LIS problem is essentially a partial order problem. Previously, in two-dimensional partial order problems, we mentioned that a Fenwick tree can easily solve such problems. However, in the previous problems, we were counting the number of pairs, not the length of sequences. To find the length of sequences, we need to modify the Fenwick tree structure.

We can use a Fenwick tree to store the maximum value of increasing subsequences ending at index . The modification of the Fenwick tree structure is as follows:

void update(int i, int k) {
    i++;
    while (i <= N) {
        node[i] = max(k, node[i]);
        i += lowbit(i);
    }
}
int sum(int i) {
    int sum = 0;
    while (i > 0) {
        sum = max(sum, node[i]);
        i -= lowbit(i);
    }
    return sum;
}

Then, we traverse the array in the same way as with , and we can obtain the correct result. Also, we need to pay attention to data discretization. The code is as follows:

class Fenwick {
public:
    int N;
    vector<int> node;

    Fenwick(int n) : N(n), node(n + 1, 0) {}

    int lowbit(int i) {
        return i & -i;
    }

    void update(int i, int k) {
        i++;
        while (i <= N) {
            node[i] = max(k, node[i]);
            i += lowbit(i);
        }
    }
    
    int sum(int i) {
        int sum = 0;
        while (i > 0) {
            sum = max(sum, node[i]);
            i -= lowbit(i);
        }
        return sum;
    }
};

class Solution {
public:
    int lengthOfLIS(vector<int> &nums) {
        int n = nums.size();
        int res = 0;
        vector<int> l = nums;
        sort(l.begin(), l.end());
        l.erase(unique(l.begin(), l.end()), l.end());
        Fenwick f = Fenwick(l.size());
        for (int i = 0; i < n; i++) {
            nums[i] = lower_bound(l.begin(), l.end(), nums[i]) - l.begin();
            res = max(res, f.sum(nums[i]) + 1);
            f.update(nums[i], f.sum(nums[i]) + 1);
            cout << i << f.sum(nums[i]) + 1 << endl;
        }
        return res;
    }
};

The time complexity of this solution is .