动态规划DP入门问题----最大连续子序列，最长不下降子序列（可以不连续），最长公共子序列

一、最大连续子序列

1.题目叙述

对于一个数字序列A1A2A3...An,求出连续子序列的最大和，如对于序列-2,11，-4,13，-5，-2，其中的最大序列和是11+（-4）+13=20

2.动态规划解法

将问题拆分成子问题，即dp[i]表示以A[i]为结尾的子序列的最大和，最后对于这些dp数组找出最大值即可，状态转移方程为：

dp[i] = max{ dp[i-1] + A[i] }  状态dp[i]表示，当前以A【i】结尾的子序列的最大和3.方法一是经典算法，方法二是根据状态方程优化而来。

#include<iostream>

#include<algorithm>

using namespace std;

int maxSum1(int arr[],int n){

    int dp[10];

    int ans = INT32_MIN;

    dp[0] = arr[0];//初始化

    for(int i=1;i&lt;n;i++){

        dp[i] = max(dp[i-1]+arr[i], arr[i]);

        ans = max(ans,dp[i]);

    }

    return ans;

}

int maxSum2(int arr[],int n){

    int dp = arr[0];

    int m = arr[0];

    for(int i=1;i&lt;n;i++){

        if(dp&lt;0){

            dp = arr[i];

        }

        else dp+=arr[i];

        if(dp&gt;m){

            m = dp;

        }

    }

    return m;

}

int main(){

    //-2,6,-1,5,4,-7,2,3

    //dp[i] = max{dp[i-1]+A[i], A[i]}

    int arr[8]={-2,6,-1,5,4,-7,2,3};

    cout<<"algorithm 1:" <<maxSum1(arr,8)<<endl;

    cout<<"algorithm 2: "<<maxSum2(arr,8)<<endl;

    return 0;

}

二、最长公共子序列（可以不连续）

状态转移函数：

if(a == b)

    dp[i][j] = dp[i-1][j-1] + 1;

else{

    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

}

for(int i=1; i<=n1; i++){

            for(int j=1; j<=n2; j++){

                char a = text1[i-1];

                char b = text2[j-1];

                if(a == b)

                    dp[i][j] = dp[i-1][j-1] + 1;

                else{

                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

                }

            }

        }

观察可以发现空间可以使用两个一维数组即可

for(int i=1; i<=n1; i++){

            for(int j=1; j<=n2; j++){

                char a = text1[i-1];

                char b = text2[j-1];

                if(a == b)

                    dp[i%2][j] = dp[(i+1)%2][j-1] + 1;

                else{

                    dp[i%2][j] = max(dp[(i+1) % 2][j], dp[i][j-1]);

                }

            }

        }

三、最长单调递增序列

状态转移方程：

dp[i]=max(dp[j])+1,其中0≤j<i且num[j]<num[i]

class Solution {

public:

    int lengthOfLIS(vector<int>& nums) {

        vector<int> dp(nums.size());

        dp[0] = 1;

        int ans = 1;

        for(int i=1; i<nums.size(); i++){

            int cur_max = 0;

            for(int j=0; j<i; j++){

                if(nums[j] < nums[i])

                    cur_max = max(cur_max, dp[j]);

            }

            dp[i] = cur_max + 1;

            cout<<dp[i]<<" ";

            ans = max(ans, dp[i]);

        }

        return ans;

    }

};

时间复杂度\(O(n^2)\)

也可以使用贪心加二分的方法，基本思路举个例子就比较容易明白，比如序列是78912345，前三个遍历完以后tail是789，这时候遍历到1，就得把1放到合适的位置(使用二分），于是在tail二分查找1的位置，变成了189（如果序列在此时结束，因为res不变，所以依旧输出3），再遍历到2成为129，然后是123直到12345 .

动态规划DP入门问题----最大连续子序列，最长不下降子序列（可以不连续），最长公共子序列的相关教程结束。