文章目录
  1. 1. 最长上升子序列
    1. 1.1. 性质
    2. 1.2. 二分复杂度优化 O(nlogn)
    3. 1.3. 例题1:拦截导弹
    4. 1.4. 例题2:最少拦截系统
    5. 1.5. 例题3:Wooden Sticks
  2. 2. 最长公共子串(dp) O(n^2)
  3. 3. 最长公共子序列 O(n^2)
  4. 4. 最长公共上升子串 O(n^2)
  5. 5. 最长公共上升子序列 O(n^2)
    1. 5.1. 变式:最长公共连续上升子序列
      1. 5.1.1. 题目要求
      2. 5.1.2. 解题思路
  6. 6. 最大子段和
    1. 6.1. 算法1:分治策略递归求解 O(nlogn)
    2. 6.2. 算法2:动态规划求解 O(n)
  7. 7. 最大M子段和 O(n^2)

引言:打了一场DP赛才发现自己的DP是如此的蒟蒻。

本文涉及:

  • 最长上升子序列,二分优化及变形
  • 最长公共子串
  • 最长公共子序列
  • 最长公共上升子串
  • 最长公共上升子序列
  • 最大子段和
  • 最大M子段和

写完这些只是帮助我记背的,本蒟蒻还是不会DP。

更新于2019年7月18日


最长上升子序列

性质

  • Dilworth定理:最长上升子序列的长度等于非上升子序列的最小划分个数(划分是指不重叠,最小划分含义为划分个数不能再少了)

    相似的,最长非下降子序列的长度等于下降子序列的最小划分个数,最长下降子序列的长度等于非下降子序列的最小划分个数……

    简单证明见下面例题2。

  • 参考:https://blog.csdn.net/xuzengqiang/article/details/7266034

  • 一个反链A是X的一个子集,它的任意两个元素都不能进行比较。

    一个链C是X的一个子集,它的任意两个元素都可比。

  • 定理1 令(X,≤)是一个有限偏序集,并令r是其最大链的大小。则X可以被划分成r个但不能再少的反链。

  • 定理2 令(X,≤)是一个有限偏序集,并令m是反链的最大的大小。则X可以被划分成m个但不能再少的链。

二分复杂度优化 O(nlogn)

  • 最长上升子序列STL二分模板(非严格递增改为upper_bound):
1
2
3
4
5
6
7
8
9
10
11
int LIS()
{
memset(dp,INF,sizeof(dp));
for(int i=0;i<n;i++)
{
int *p=lower_bound(dp,dp+n,a[i]);
*p=a[i];
maxlen[i]=p-dp+1;//存储以a[i]为尾元素的最长上升子序列的长度
}
return lower_bound(dp,dp+n,INF)-dp;
}
  • 最长 ?? 子序列STL二分模板全家桶:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<cstring>
#include<algorithm>
#include<iostream>
#define INF 0x3f3f3f3f
using namespace std;
int dp[10001];
int maxlen[10001];
int a[10001] = { 9,9,2,5,5,4 };
template<class comp>
int LS(int *a, int n, comp cmp, int INIT)
{
int maxl = 0;
memset(dp, INIT, sizeof(dp));
for (int i = 0; i<n; i++)
{
int *p = lower_bound(dp, dp + n, a[i], cmp);
*p = a[i];
maxlen[i] = p - dp + 1;//存储以a[i]为尾元素的最长子序列的长度
maxl = max(maxl, maxlen[i]);
}
return maxl;
}
int main(void)
{
cout << LS(a, 6, less<int>(), INF) << endl;//严格上升
cout << LS(a, 6, less_equal<int>(), INF) << endl;//非严格上升
cout << LS(a, 6, greater<int>(), -INF) << endl;//严格下降. 在降序数组中查找第一个匹配(精准覆盖)
cout << LS(a, 6, greater_equal<int>(), -INF) << endl;//非严格下降. 在降序数组中查找最右匹配+1(避免覆盖)
return 0;
}
  • 开辟一个新数组,在里面顺次对每个元素进行二分查找并填充元素,填充的位置+1即以该元素结尾的最长子序列长度。
  • 注意,在排序时,greater是升序排序;在查找时,greater适用于降序数组。
  • 以下例题都是O(n2)O(n^2)的做法,都可以用模板优化。

例题1:拦截导弹

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[10001];
int dp[10000];
int solve(int *a,int n)
{
int maxn=0;
for(int i=0;i<n;i++)
{
dp[i]=1;
for(int j=0;j<i;j++)
{
if(a[i]<=a[j])//注意,此题求的是可拦截的最大导弹,因此应该是求最长非升子序列
dp[i]=max(dp[i],dp[j]+1);
}
maxn=max(maxn,dp[i]);
}
return maxn;
}

int main(void)
{
int n;
while(scanf("%d",&n)==1)
{
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
printf("%d\n",solve(a,n));
}
return 0;
}

例题2:最少拦截系统

  • 这是一道性质的应用。让求非升子序列的最小划分,那么到底等不等于最长上升子序列的长度呢?

    https://blog.csdn.net/litble/article/details/85305561

    如果有a是导弹抵达时间,b是高度,那么定义偏序关系为a1<a2且b1>=b2,求该偏序关系上的链的最小划分,即求反链的最大集合长度。

    证明:反链即这样的一个集合,该集合上任意两个元素都不满足偏序关系,即任意两个导弹都不满足(a1<a2且b1>=b2)或(a2<a1且b2>=b1),即任意两个导弹都要满足(a1>=a2或b1<b2)且(a2>=a1或b2<b1),即任意两个导弹都要满足(a1>=a2或b1<b2)且(a1<=a2或b1>b2)。当a1==a2时成立,但由于没有两个导弹会同时到达,因此a1==a2的情况排除;当a1!=a2时,需要满足(a1>a2且b1>b2)或(a1<a2且b1<b2),显然等价于严格上升关系。

    所以应求最长上升子序列的长度。

  • 传送门:HDU - 1257

  • AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<limits.h>
#define max(x,y) ((x)>(y)?(x):(y))
int dp[10000];
int a[10001];
int LIS(int *a,int n)
{
int maxn=0;
for(int i=0;i<n;i++)
{
dp[i]=1;
for(int j=0;j<i;j++)
{
if(a[i]>a[j])
dp[i]=max(dp[i],dp[j]+1);
}
maxn=max(maxn,dp[i]);
}
return maxn;
}
int main(void)
{
int n;
while(scanf("%d",&n)==1)
{
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
printf("%d\n",LIS(a,n));
}
return 0;
}

例题3:Wooden Sticks

  • 这是一道性质的应用,如果用二分优化复杂度可以优化到O(nlogn)O(nlogn)。当然也可以贪心去做。
  • 这道题是求非降子序列的最小划分,即求下降子序列的最大长度。二分优化使用greater<int>()​
  • 传送门:HDU - 1051
  • AC代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cctype>
#include<cstring>
#include<cmath>
#include<algorithm>
typedef long long ll;
using namespace std;
inline int read()
{
int a=0, f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1; c=getchar();}
while(isdigit(c)) (a*=10)+=c-'0', c=getchar();
return a*f;
}
struct s
{
int a,b;
}st[10010];
bool cmp(s a,s b)
{
if(a.a==b.a)
return a.b<b.b;
return a.a<b.a;
}
int dp[10010],n;
int LDS()
{
for(int i=0;i<n;i++)
dp[i]=1;
for(int i=0;i<n;i++)
{
for(int j=0;j<i;j++)
{
if(st[j].b>st[i].b)
dp[i]=max(dp[i],dp[j]+1);
}
}
int m=0;
for(int i=0;i<n;i++)
m=max(dp[i],m);
return m;
}
int main(void)
{
int T=read();
while(T--)
{
n=read();
for(int i=0;i<n;i++)
{
st[i].a=read();
st[i].b=read();
}
sort(st,st+n,cmp);
/*for(int i=0;i<n;i++)
printf("%d,%d\n",st[i].a,st[i].b);*/
printf("%d\n",LDS());
}
return 0;
}

最长公共子串(dp) O(n^2)

  • 对了,这个做法是O(n2)O(n^2)的,但是用后缀数组+高度数组可以降到O(nlog2n)O(nlog^2 n )这里不提。

  • 附上滚动数组DP代码(下标从1开始):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[210];
int main()
{
char s1[]=" ider.cs@gmail.com";
char s2[]=" blog.iderzheng.com";
int len1=strlen(s1),len2=strlen(s2);
int maxn=0;
for(int i=1;i<len1;i++)
{
dp[0]=0;
for(int j=len2-1;j>=1;j--)
{
if(s1[i]==s2[j])
dp[j]=dp[j-1]+1;//注意内层循环的方向
else
dp[j]=0;//丢掉之前的状态不保留
}
for(int j=1;j<len2;j++)
printf("%d ",dp[j]);
putchar('\n');
}
printf("%d\n",maxn);
return 0;
}

代码中需要注意的是内层循环需要从右向左进行,这样才能不损失dp[j-1]这个状态。

最长公共子序列 O(n^2)

  • 这个无疑是最长公共子串的升级版了,可以对比来学习。

  • 参考博文:最长公共子序列(LCS)问题 ,先上这个很经典的图:

  • 从图中很清楚可以看到和最长公共子串的区别在于,它是:

    • 如果str1[m] == str2[n],则L[m,n] = L[m - 1, n -1] + 1 ;
    • 如果str1[m]/=str2[n]str1[m] \rlap{\,/}{=} str2[n],则L[m,n]=max( L[m,n1], L[m1,n] )L[m,n] = max ( ~ L[m,n - 1], ~L[m - 1, n] ~ )

    即如果不相等,保存前一个状态,以备相等时候的使用。并且这样某点的值必定不小于其左、上、左上的所有元素(好像这个结论并没有什么卵用)。

  • 博文介绍了一种二维数组的方法,这里贴一个滚动数组的(下标从1开始):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[210][2];
int main()
{
char s1[]=" ABCBDAB";
char s2[]=" BDCABA";
int len1=strlen(s1),len2=strlen(s2);
int maxn=0;
memset(dp,0,sizeof(dp));
for(int i=1,sta=0;i<len1;i++,sta=!sta)
{
for(int j=1;j<len2;j++)//注意变量初值
{
if(s1[i]==s2[j])
dp[j][sta]=dp[j-1][!sta]+1;
else
dp[j][sta]=max(dp[j-1][sta],dp[j][!sta]);//保留上方和左方的状态
printf("%d ",dp[j][sta]);
maxn=max(maxn,dp[j][sta]);
}
putchar('\n');
}
printf("%d\n",maxn);
return 0;
}

最长公共上升子串 O(n^2)

  • 理解了最长上升字串,看懂图之后这个应该不难写。

  • 先贴非滚动数组的代码(下标从1开始):

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    #define _CRT_SECURE_NO_WARNINGS
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    int dp[210][210];
    int main()
    {
    int a1[]={-1,1,5,6,7,2,1,10,5};
    int a2[]={-1,2,1,10,5,6,7,5};
    int len1=sizeof(a1)/sizeof(int),len2=sizeof(a2)/sizeof(int);
    int maxn=0;
    for(int i=1;i<len1;i++)
    {
    for(int j=1;j<len2;j++)
    {
    if(a1[i]==a2[j])
    if(a1[i]>a1[i-1])
    dp[i][j]=dp[i-1][j-1]+1;
    else
    dp[i][j]=1;
    else
    dp[i][j]=0;
    maxn=max(maxn,dp[i][j]);
    printf("%d ",dp[i][j]);
    }
    putchar('\n');
    }
    printf("%d\n",maxn);
    return 0;
    }
  • 讲一下滚动数组优化思路:很容易看出可以优化为2×n的二维数组,因为dp数组只跟i,j,i1,j1i,j,i-1,j-1有关,但也可以滚动成一维数组,因为发现它优化成一维数组没有障碍。它与i1,j1i-1,j-1相关,那么我们可以让内层循环从右往左循环,就可以保留上(指dp[i1][j]dp[i-1][j])和左上(指dp[i1][j1]dp[i-1][j-1])的状态了。

  • 一维数组滚动代码(下标从1开始):

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    #define _CRT_SECURE_NO_WARNINGS
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    int dp[210];
    int main()
    {
    int a1[]={-1,1,5,6,7,2,1,10,5};
    int a2[]={-1,2,1,10,5,6,7,5};
    int len1=sizeof(a1)/sizeof(int),len2=sizeof(a2)/sizeof(int);
    int maxn=0;
    for(int i=1;i<len1;i++)
    {
    for(int j=len2-1;j>=1;j--)
    {
    if(a1[i]==a2[j])
    if(a1[i]>a1[i-1])
    dp[j]=dp[j-1]+1;
    else
    dp[j]=1;
    else
    dp[j]=0;
    maxn=max(maxn,dp[j]);
    printf("%d ",dp[j]);
    }
    putchar('\n');
    }
    printf("%d\n",maxn);
    return 0;
    }

最长公共上升子序列 O(n^2)

  • 这个又提升了难度。

  • 贴个滚动数组的代码(下标从1开始):

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    #define _CRT_SECURE_NO_WARNINGS
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    int dp[210];
    int main()
    {
    int a1[]={-1,1,5,6,7,2,1,10,5};
    int a2[]={-1,2,1,10,5,6,7,5};
    int len1=sizeof(a1)/sizeof(int),len2=sizeof(a2)/sizeof(int);
    int maxn=0;
    for(int i=1;i<len1;i++)
    {
    int m=0;
    for(int j=1;j<len2;j++)
    {
    if(a1[i]>a2[j])
    m=max(m,dp[j]);
    else if(a1[i]==a2[j])
    dp[j]=m+1;
    }
    }
    for(int j=0;j<len2;j++)
    maxn=max(maxn,dp[i]);
    printf("%d\n",maxn);
    system("pause");
    return 0;
    }
  • 看起来似乎很难以理解。这里有两种状态,一个是公共,一个是上升。其实它是将状态转移分离了,考虑这种情况:假设i=3,相应值是6,我们假定DP在运行到i=3之前都能正常工作,那么我从0到len2对序列2扫一遍,之前肯定有dp[1]=1,dp[4]=2(dp[j]表示以a2[j]结尾的最长公共子序列长度)。于是我在扫的过程中找到了a1[3]>a2[1],m存上1,又找到a1[3]>a2[4],m存上2,等到a1[3]==a2[5]的时候,我再开始转移,从dp[4]转移到dp[5],dp[5]变成了3。

  • 也就是说,只要dp[j]不为0,那a1[i]>a2[j]就保证了a1[i]>a1[k],其中a1[k]==a2[j],就保证了上升,a1[i]==a2[j]就保证了公共,dp状态的保存转移就保证了子序列。

  • 于是我想出一道变式,有兴趣的可以推一下:

变式:最长公共连续上升子序列



题目要求

  • 给出两个整数序列,求出其公共的连续上升数字的子序列的长度。

    {1,4,2,0,3,9,4,5}\lbrace 1,4,2,0,3,9,4,5 \rbrace{0,2,9,3,7,5,10}\lbrace 0,2,9,3,7,5,10 \rbrace的最长公共连续上升子序列为{2,3}\lbrace 2,3 \rbrace长度。


解题思路

  • 这道题仍然有两个状态,一个是公共,一个是连续上升,特性是子序列。其实你只要会了最长公共上升子序列,这道题就很容易推出来了。

  • 贴个滚动数组代码(下标从1开始):

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    #define _CRT_SECURE_NO_WARNINGS
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    int dp[210];
    int main()
    {
    int a1[]={-1,1,4,2,0,3,9,4,5};
    int a2[]={-1,0,2,9,3,7,5,10};
    int len1=sizeof(a1)/sizeof(int),len2=sizeof(a2)/sizeof(int);
    int maxn=0;
    for(int i=1;i<len1;i++)
    {
    int m=0;
    for(int j=1;j<len2;j++)
    {
    if(a1[i]==a2[j]+1)
    m=max(m,dp[j]);
    else if(a1[i]==a2[j])
    dp[j]=m+1;
    }

    }
    for(int j=0;j<len2;j++)
    maxn=max(maxn,dp[j]);//不要在外层循环滚动求最大值
    printf("%d\n",maxn);
    system("pause");
    return 0;
    }

最大子段和

算法1:分治策略递归求解 O(nlogn)

  • 用分治法递归,问题分解为:

    1. 求左半区域的最大子数组
    2. 求跨越中值的最大子数组
    3. 求右半区域的最大子数组

    由于当问题微分触底,1和3将被包含在2中,因此分解、解决、合并的步骤中,合并时只需要求2即可。

  • 算法导论4.1股票买卖:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
/*
【问题】
算法导论4.1股票买卖:给出一个数组显示某公司17天每天股票的价格,假设你可以在任意一天结束时买入或卖出股票(只能进行一组买入及卖出),求最大收益及买卖日期。要求时间复杂度为o(n²)。

int A[17]={100,113,110,85,105,102,86,63,81,101,94,106,101,79,94,90,97};

分治法复杂度O(nlogn)
*/
#include<stdio.h>
#define INF 0x3F3F3F3F
typedef struct {
int left;
int right;
int sum;
}structRet;

structRet FindMaxCrossingSubarray(int *Array, int left, int middle, int right)
{
int sum = 0,leftsum=-INF,rightsum=-INF,maxleft,maxright;
for (int i = middle; i >= left; i--)
{
sum += Array[i];
if (sum > leftsum)
{
leftsum = sum;
maxleft = i;
}
}
sum = 0;
for (int i = middle+1; i<= right; i++)
{
sum += Array[i];
if (sum > rightsum)
{
rightsum = sum;
maxright = i;
}
}
return structRet{ maxleft, maxright, leftsum + rightsum };
}
structRet FindMaxSubarray(int *Array, int left, int right)
{
if (left >= right)
return structRet{ left,right,Array[left] };
int middle = (left + right) / 2;
structRet ret1, ret2, ret3;
ret1=FindMaxSubarray(Array, left, middle);
ret2=FindMaxSubarray(Array, middle+1, right);
ret3=FindMaxCrossingSubarray(Array, left, middle, right);
if (ret1.sum >= ret2.sum)
{
if (ret1.sum >= ret3.sum)
return ret1;
else
return ret3;
}
else if (ret2.sum >= ret3.sum)
return ret2;
else
return ret3;

}

int main(void)
{
int _A[17] = { 100,113,110,85,105,102,86,63,81,101,94,106,101,79,94,90,97 };
int A[16] = { 13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7 };
int B[6] = { -3,-5,-1,-7,-2,-8 };
structRet ret=FindMaxSubarray(B, 0, 5);
return 0;
}

算法2:动态规划求解 O(n)

  • 问题转化为找出最大子数组。用动态规划,假设尾部添加新的元素,则最大子数组将在不包含新元素的最大子数组和包含新元素的最大子数组中产生,其中包含新元素的最大子数组的状态转移方程为

    dp[i]=max(dp[i1]+a[i],a[i])dp[i]=max(dp[i-1]+a[i],a[i])

  • 编程之美给出了及其优美的线性解法:

1
2
3
4
5
6
7
8
9
10
11
int dpFindMaxSubarray(int *A, int n)    //动态规划 
{
int nAll = A[0]; //当前最大子段的和
int nEnd = 0; //以A[i]结尾的子数组最大和
for (int i = 0; i < n; i++)
{
nEnd = max(A[i], nEnd + A[i]); //求以A[i]结尾的和最大的子数组
nAll = max(nAll, nEnd); //当前和最大子段要么是以A[i]结尾,要么和A[i]无关
}
return nAll;
}

最大M子段和 O(n^2)

  • 简直是本专题完美的究极奥义啊,它帮我进一步完善了我蒟蒻的DP脑残思想,动态规划是指,通过一个正确的动态转移方程求得解,不管dp数组是一维还是二维还是三维的,只要在方程里ijk是变的,那就没错了。

    经典例题: A - Max Sum Plus Plus HDU - 1024

  • 看了题你大概就知道最大M子段和是啥意思了。

  • 动态转移方程:

dp[i][j]=max(dp[i][j-1]+a[i],max(dp[0][j-1]dp[i-1][j-1])+a[i])\text{dp[i][j]=max(dp[i][j-1]+a[i],max(dp[0][j-1]} \sim \text{dp[i-1][j-1])+a[i])}

  • 其中ii是段数,jj是以jj为结尾(必须包含jj)。那么开始考虑分成ii段的时候,以jj结尾的话,要么a[j]a[j]被包含在最后一段里(即dp[i][j1]+a[i]\color{grey}{dp[i][j-1]+a[i]}),要么jj独自成段。如果jj独自成段,就从i1i-1段的状态里面找个最大值转移过来(即max{dp[0][j1]dp[i1][j1]}+a[i]\color{grey}{max\{dp[0][j-1] \sim dp[i-1][j-1]\}+a[i]})。如果直接做是O(n3)O(n^3)的,但找最大值的这里可以进行滚动,将时间复杂度压为O(n2)O(n^2)

  • 在将算法转化为代码的过程中,我感觉最为困难的是将最大值转移的那一块,我找到了一个将lmax开成[1000010][2]的滚动数组的方法,但总认为不好,于是在这部分借鉴了一下网上的做法,我觉得十分巧妙。

  • 贴上代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int a[1000010];
int dp[1000010];
int m,n;
int lmax[1000010]; //lmax[n]是指上一轮里dp[1]~dp[n]里面的最大值
int solve()
{
fill(dp,dp+n+1,0);
fill(lmax,lmax+n+1,0);
int tmp;
for(int i=1;i<=m;i++)//分为i段
{
tmp=-INF;
for(int j=i;j<=n;j++)//这里必须注意j的初值,因为如果分i段的话,是不可能以a[1]~a[i-1]结尾的
{
dp[j]=max(dp[j-1],lmax[j-1])+a[j];//这里需要lmax[j-1]是上一轮的,所以下面一条赋值的下标就不能领先它的下标,否则就提前更新了
lmax[j-1]=tmp;//lmax肯定最多只需要1~n-1就可以了,所以不必写lmax[j]=max(lmax[j-1],dp[j]),这样就领先了,无法进行滚动
tmp=max(tmp,dp[j]);//巧妙借助一个tmp变量,延时赋值
}
}
return tmp;
}
int main(void)
{
while(scanf("%d %d",&m,&n)==2)
{
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
printf("%d\n",solve());
}
return 0;
}
文章目录
  1. 1. 最长上升子序列
    1. 1.1. 性质
    2. 1.2. 二分复杂度优化 O(nlogn)
    3. 1.3. 例题1:拦截导弹
    4. 1.4. 例题2:最少拦截系统
    5. 1.5. 例题3:Wooden Sticks
  2. 2. 最长公共子串(dp) O(n^2)
  3. 3. 最长公共子序列 O(n^2)
  4. 4. 最长公共上升子串 O(n^2)
  5. 5. 最长公共上升子序列 O(n^2)
    1. 5.1. 变式:最长公共连续上升子序列
      1. 5.1.1. 题目要求
      2. 5.1.2. 解题思路
  6. 6. 最大子段和
    1. 6.1. 算法1:分治策略递归求解 O(nlogn)
    2. 6.2. 算法2:动态规划求解 O(n)
  7. 7. 最大M子段和 O(n^2)