一维动态规划模板

#include <bits/stdc++.h>
using namespace std;

// 最长上升子序列 LIS
int lis(int a[], int n) {
    vector<int> dp;
    for (int i = 0; i < n; i++) {
        auto it = lower_bound(dp.begin(), dp.end(), a[i]);
        if (it == dp.end()) dp.push_back(a[i]);
        else *it = a[i];
    }
    return dp.size();
}

// 最大子段和（Kadane 算法）
int maxSubArray(int a[], int n) {
    int maxSum = a[0], curSum = a[0];
    for (int i = 1; i < n; i++) {
        curSum = max(a[i], curSum + a[i]);
        maxSum = max(maxSum, curSum);
    }
    return maxSum;
}

// 最长公共子序列 LCS
int lcs(string &a, string &b) {
    int n = a.size(), m = b.size();
    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            dp[i][j] = a[i-1]==b[j-1] ? dp[i-1][j-1]+1 : max(dp[i-1][j], dp[i][j-1]);
    return dp[n][m];
}

int main() {
    int a[] = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << lis(a, 8) << endl;  // 4  (2,3,7,101)
    return 0;
}

📖 要点说明

• LIS 贪心+二分优化到 O(n log n)
• Kadane：curSum = max(a[i], curSum+a[i])
• LCS 用二维 DP，空间可优化到一维

⚠️ 常见错误

• LIS 的 O(n²) 写法超时
• Kadane 初始值设0（应为 a[0]）
• LCS 下标从1还是0搞混