Dynamic Programming Techniques and Classic Problems
Linear DP
Longest Increasing Subsequence (LIS)
Achieves O(n log n) time complexity using binary search:
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> seq(n);
for (auto &x : seq) cin >> x;
vect ...
Posted on Thu, 24 Sep 2026 16:01:40 +0000 by Wldrumstcs