SkyLee炒股票（最大连续子序列和）

这道题其实用DP有点浪费的感觉，其实这道题用简单的遍历法也可以，不过实质上还是DP思想的进阶。

这道题如何设置DP数组？我们不妨设置DP[i]为以数组元素ar[i]结尾的连续序列的最大和.

所以我们很容易得出状态转移方程：

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

倘若之前的dp[i-1]再加上当前元素得到的值更大，那么最大连续子序列的长度就会延长，如果没有那么就可以使其单个元素成为一个连续子序列。

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int Maxlen = 1e6 + 10;
long long num[Maxlen];
long long dp[Maxlen];//dp[i]代表的是以i元素结尾的连续子序列的最大值
int main(int argc, char *argv[]) {
    
    int n,i,j,k;
    long long ans;
    while(~scanf("%d",&n)){
        for(i=1;i<=n;i++)
            scanf("%lld",&num[i]);
            dp[0]=0;
            ans=0;
        for(i=1;i<=n;i++){
            dp[i]=max(dp[i-1]+num[i],num[i]);
            ans=max(ans,dp[i]);
        }
        printf("%lld
",ans);
    }
    return 0;
}

那如果我们要继续求解最大连续子序列和的起点和终点的位置呢？

显然只需要利用dp数组进行一次搜索即可。

            if(dp[i]>ans){
                ans=dp[i];
                right=i;
                left=i;
                while(dp[left] > 0 && left >=1)
                    left--;
                if(left ==0 || dp[left] < 0)
                    left++;
            }

接下来再来求解一道经典的序列DP 问题 LIS

ModricWang的导弹拦截系统（最长不上升子序列 LIS）

这道题其实就是求解最长不上升子序列长度。

我们首先思考DP数组的设置：dp[i]代表的是以数组元素ar[i]为结尾元素的不上升子序列长度。

那转移方程呢？

for(i=1;i<=n;i++){
        for(j=1;j<i;j++){
            if(ar[j]>=ar[i])
                dp[i]=max(dp[j]+1,dp[i]);
        }
        ans=max(ans,dp[i]);
    }

其实到这一步就可以简单的总结一下序列DP的解法。

做DP题的第一步就是合理的构造有确定含义符合最优子结构的DP数组

然后是实现状态转移方程，其第一步的构思和第二部略有重复。最后实现一下DP数组的初始化，就可以完成了。

序列DP的dp数组的设置通常具有的含义是以给定数组ar[i]结尾的具有某种特殊含义的数组，然后继续思考状态转移方程即可。

由于序列只有前后的逻辑关系，所以子问题和父问题，可以简单的理解为前后关系。

同时序列DP的最值问题，通常在遍历求解DP数组的同时，更新即可。

最长公共子序列（LCS）

给定两个序列，求解最长公共子序列的问题。

根据上述设置dp数组的思路我们不妨设置 dp[i][j] 其中i为序列1 以下标i结尾 j为序列2 以下标j结尾

状态转移方程：

 if(s1[i]==s2[j])
                dp[i][j]=dp[i-1][j-1]+1;
            else
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);

最长上升公共子序列（LCIS）

http://acm.hdu.edu.cn/showproblem.php?pid=1423（原题链接）

显然这道题是基与LCS的，那么如何求解上升的子问题，我们还是按照序列dp一贯的思路设置dp数组：

设置 dp[i][j] 其中i为序列1 以下标i结尾 j为序列2 以下标j结尾显然这些是不够的

我们在此之上可以添加一点条件：我们不妨设置dp[i][j]的公共子序列的末尾元素是dp[j]即：

dp[i][j]表示以a串的前i个整数与b串的前j个整数且以b[j]为结尾构成的LCIS的长度

那么我们来实现状态转移方程：

    if(a[i] != b[j])
        dp[i][j]=dp[i-1][j];
    else {
        for(k=1;k<=j-1;k++)
            if(b[j]>b[k])
                dp[i][j]=max(dp[i][j],dp[i-1][k]+1);
    }

从这道题我们可以总结出来序列DP的一些其他思想，如果存在两个以上变化的量，我们可以考虑以一个变量为标准，相当于确定了一个变量，这样思考另一个变量带来的影响更简洁。

中等·Bamboo's Fight with DDLs II (类似LCS的序列DP问题)

dp[i][j]代表的是序列区间是从i到j的最长回文子序列长度

                if(str[i] == str[j])
                    dp[i][j]=2+dp[i+1][j-1];
                else dp[i][j]=max(dp[i+1][j],dp[i][j-1]);