动态规划--最大字段和、最长上升子序列、最长公共子序列

最大字段和、最长上升子序列。最长公共子序列是经典的dp问题

最大字段和：

简单来说就是求序列中子序列和的最大值

对于非正数的序列，答案ans就是其中的元素的最大值；

对于有正数的序列，考虑以每一个点为结尾的最大子段和，这个子段一定满足其前缀和均非负，因为如果有一个前缀是负的，那么减掉这个前缀对于这个点一定更优，

#include<iostream>
#include<algorithm>
using namespace std;
const int inf = 0x7fffffff;
int num[101];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> num[i];
    }
    int ans = -inf;          //ans 取一个最小值 
    for (int i = 0; i < n; i++) {
        ans = max(ans, num[i]);    //ans为数组中最大的那个值 
    }
    if (ans <= 0) { 
        cout << ans << endl;      //如果数组中的数都为负数，那么ans的值为数组中的最大值 
    }
    else {                       //数列中不全是负数 
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (sum + num[i] < 0) {          //字段和小于0，将sum为0 
                sum = 0;
            }
            else {                  
                sum += num[i];          //更新字段和 
            }
            ans = max(ans, sum);        //ans取较大的值 
        }
        cout << ans << endl;
    }
    return 0;
}

最长上升子序列（LIS）：

dp[i]表示一定以第i项为结尾的最长上升子序列，a[i]表示第i项的值，如果有j < i 且a[j] < a[i],

那dp[i] = dp[j] + 1

状态转移方程 dp[i] = max(dp[i], dp[j] + 1)

时间复杂度为O(N2)

#include<iostream>
#include<algorithm>
using namespace std;
int a[1010];
int dp[1010];
int main() {
    int n ;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int ans = 0;           
    for (int i = 1; i <= n; i++) {
        dp[i] = 1;                    
        for (int j = 1; j < i; j++) {
            if (a[j] < a[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        ans  = max(ans, dp[i]);
    }
    cout << ans << endl;
    return 0;
} 

最长公共子序列（LCS）：

dp[i][j]表示子序列xi 和yj 的最长公共子序列的长度，

当xi = yj 时，找出xi-1 和 yj-1 的最长公共子序列，然后在尾部加上xi, 即可得到x和y的LCS

当xi != yj时， 求max(xi-1 和yj 的LCS， xi 和yj-1 的LCS)

#include<iostream>
#include<cstring>
using namespace std;
int dp[110][110];
int main() {
    string a, b;
    memset(dp, 0, sizeof (dp));
    cin >> a >> b;
    int lena = a.size();
    int lenb = b.size();
    for (int i = 1; i <= lena; i++) {
        for (int j = 1; j <= lenb; j++) {
            if (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    cout << dp[lena][lenb] << endl;
    return 0;
}