int arr[1000000];
int dp[1000000];
int main(){
int N;
while(scanf("%d",&N)!=EOF){
for(int i=0;i<N;i++){
cin>>arr[i];
}
dp[0]=arr[0];
int ans=-1000000;
for(int i=1;i<N;i++){
dp[i]=max(arr[i],dp[i-1]+arr[i]);
ans=max(ans,dp[i]);
}
cout<<ans<<endl;
}
return 0;
}
最大序列和：https://www.nowcoder.com/practice/df219d60a7af4171a981ef56bd597f7b
最大子矩阵：https://www.nowcoder.com/practice/a5a0b05f0505406ca837a3a76a5419b3
该题为典型的变形题，附模板：
思路：设最大子矩阵所在行为i到j，会有两种情况：
#include<iostream>
#include<cstdio>
using namespace std;
int matrix[110][110];
int total[110][110];
int arr[110];
int dp[110];
int MaxSubSequence(int n){
int maxi=0;
dp[0]=arr[0];
for(int i=1;i<n;i++){
dp[i]=max(dp[i-1]+arr[i],arr[i]);
maxi = max(maxi,dp[i]);
}
return maxi;
}
int MaxSubMatrix(int n){
int maxi=0;
for(int i=0;i<n;i++){
for(int j=i;j<n;j++){
for(int k=0;k<n;k++){
if(i==0){
arr[k]=total[j][k];
}
else{
arr[k]=total[j][k]-total[i-1][k];
}
}
int current=MaxSubSequence(n);
maxi = max(maxi,current);
}
}
return maxi;
}
int main(){
int n;
while(scanf("%d",&n)!=EOF){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>matrix[i][j];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==0){
total[i][j]=matrix[i][j];
}
else{
total[i][j]=total[i-1][j]+matrix[i][j];
}
}
}
cout<<MaxSubMatrix(n);
}
return 0;
}
最大连续子序列：https://www.nowcoder.com/practice/afe7c043f0644f60af98a0fba61af8e7
#include<iostream>
#include<cstdio>
using namespace std;
int arr[1001];
int dp[1001];
int main(){
int n;
while(scanf("%d",&n)!=EOF){
for(int i=0;i<n;i++){
cin>>arr[i];
}
int ans=0;
for(int i=0;i<n;i++){
dp[i]=arr[i]; //本题要求的是 最长递增子序列的和是多少，否则dp[i]=1
for(int j=0;j<i;j++){
if(arr[i]>arr[j]){
dp[i]=max(dp[i],arr[i]+dp[j]);
}
}
ans = max(ans,dp[i]);
}
cout<<ans<<endl;
}
}
给出字符串S1,S2，分别求其子串（按照先后顺序，但不用连续），找出最长的公共子串
正常遍历，时间复杂度为O(2^m+n)
dp时间复杂度为O(nm)
创建二维数组dp[] []，dp[i] [j]为以S1i和S2j结尾的最长公共子序列长度，dp[n] [m]为答案
得到状态转移方程 i=j时，dp[i] [j]=dp[i-1] [j-1]+1
i！=j时，dp[i] [j]=max(dp[i-1] [j],dp[i] [j-1])
初始状态：dp[i] [0]=dp[0] [j]=0
S1,S2
二维dp数组
转移方程：
i=j时，dp[i] [j]=dp[i-1] [j-1]+1
i！=j时，dp[i] [j]=max(dp[i-1] [j],dp[i] [j-1])
初始状态：dp[i] [0]=dp[0] [j]=0
输出：dp数组[n] [m]
#include<iostream>
#include<cstdio>
using namespace std;
string s1;
string s2;
int dp[101][101];
int main(){
while(cin>>s1>>s2){
int n=s1.length();
int m=s2.length();
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
if(i==0||j==0){
dp[i][j]=0;
continue;
}
if(s1[i-1]==s2[j-1]){ //这里一定是i-1和j-1，因为从0开始，最后输出nm
dp[i][j]=dp[i-1][j-1]+1;
}
else{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
}
cout<<dp[n][m]<<endl;
}
return 0;
}
w数组，v数组
一维dp数组
转移方程：
dp[j]=max(dp[j]，dp[j-w[i]]+v[i]) 要求倒叙查j，并且j-w[i]要大于等于0
初始状态：dp[j]=0
输出：dp[m]
#include<iostream>
#include<cstdio>
using namespace std;
int v[1001];
int w[1001];
int dp[1001];
int main(){
int n,m;
cin>>m>>n;
for(int i=0;i<n;i++){
cin>>w[i]>>v[i];
}
for(int i=0;i<=m;i++){
dp[i]=0;
}
for(int i=0;i<n;i++){
for(int j=m;j>=w[i];j--){ //倒叙！
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
cout<<dp[m]<<endl;
return 0;
}
w数组，v数组
一维dp数组
转移方程：
dp[j]=max(dp[j]，dp[j-w[i]]+v[i]) 要求顺序查j，并且j-w[i]要大于等于0
初始状态：dp[j]=0
输出：dp[m]
const int INF=0x3f3f3f3f;
int v[10010];
int w[10010];
int dp[1001000];
int main(){
int k;
cin>>k;
while(k--){
memset(v,0,sizeof(v));
memset(w,0,sizeof(w));
int a,b,ans;
cin>>a>>b;
ans=b-a;
int n;
cin>>n;
for(int i=0;i<n;i++){
cin>>v[i]>>w[i];
}
memset(dp,INF,sizeof(dp)); //初始化数组无穷大
dp[0]=0; //但是第一个一定要为0，如果不为零，那么数组中所有的数都会是无穷大的。
for(int i=0;i<n;i++){
for(int j=w[i];j<=ans;j++){ //顺序
dp[j]=min(dp[j],dp[j-w[i]]+v[i]);
}
}
if(dp[ans]!=INF){
printf("The minimum amount of money in the piggy-bank is %d.\n",dp[ans]);
}else{
cout<<"This is impossible."<<endl;
}
}
}
#include<iostream>
#include<cstdio>
using namespace std;
int v[10000];
int w[10000];
int k[10000];
int dp[10000];
int value[10000]; //分解后的v
int weight[10000]; //分解后的w
int main(){
int C;
cin>>C;
for(int i=0;i<C;i++){
int n,m;
cin>>m>>n;
int number=0; //记录分解后有几个
for(int j=0;j<n;j++){
cin>>w[j]>>v[j]>>k[j];
for(int p=1;p<=k[j];p<<=1){ //分解物品，p是2的c次方增长
value[number]=p*v[j];
weight[number]=p*w[j];
number++;
k[j]-=p;
}
if(k[j]>0){ //k-2^c+1个
value[number]=k[j]*v[j];
weight[number]=k[j]*w[j];
number++;
}
}
for(int j=0;j<=m;j++){ //初始化dp数组
dp[j]=0;
}
for(int j=0;j<number;j++){ //m是容量，number是分解后有几个物品
for(int k=m;k>=weight[j];k--){
dp[k]=max(dp[k],dp[k-weight[j]]+value[j]);
}
}
cout<<dp[m]<<endl;
}
return 0;
}
原文：https://www.cnblogs.com/LazyXx/p/14603902.html