最大子段和,最大子矩阵和,最大m子段和问题
最大子段和问题
Problem Link:http://acm.hdu.edu.cn/showproblem.php?pid=1003
Max Sum
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 322160 Accepted Submission(s): 76605
Problem Description
Given a sequence a[1],a[2],a[3]......a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.
Input
The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).
Output
For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.
Sample Input
2 5 6 -1 5 4 -7 7 0 6 -1 1 -6 7 -5
Sample Output
Case 1:
14 1 4
Case 2:
7 1 6
AC code:
#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
int a[maxn];
int n,st,ed;
int maxsum(int num[],int len)
{
int sum,res,tmp;
res=num[1];
sum=0;
tmp=st=ed=1;
for(int i=1;i<=len;i++)
{
if(sum<0)
{
sum=num[i];
tmp=i;
}
else
{
sum+=num[i];
}
if(res<sum)
{
res=sum;
st=tmp;
ed=i;
}
}
return res;
}
int main()
{
int T;
scanf("%d",&T);
for(int cas=1;cas<=T;cas++)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
int ans = maxsum(a,n);
printf("Case %d:\n%d %d %d\n",cas,ans,st,ed);
if(cas!=T)
puts("");
}
return 0;
}
最大子矩阵和问题
Problem Link:http://acm.hdu.edu.cn/showproblem.php?pid=1081
To The Max
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 16292 Accepted Submission(s): 7489
Problem Description
Given a two-dimensional array of positive and negative integers, a sub-rectangle is any contiguous sub-array of size 1 x 1 or greater located within the whole array. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle.
As an example, the maximal sub-rectangle of the array:
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
is in the lower left corner:
9 2
-4 1
-1 8
and has a sum of 15.
Input
The input consists of an N x N array of integers. The input begins with a single positive integer N on a line by itself, indicating the size of the square two-dimensional array. This is followed by N 2 integers separated by whitespace (spaces and newlines). These are the N 2 integers of the array, presented in row-major order. That is, all numbers in the first row, left to right, then all numbers in the second row, left to right, etc. N may be as large as 100. The numbers in the array will be in the range [-127,127].
Output
Output the sum of the maximal sub-rectangle.
Sample Input
4 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2
Sample Output
15
AC code:
#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
int a[maxn][maxn];
int n;
int maxsum(int num[],int len)
{
int sum,res;
res=num[1];
sum=0;
for(int i=1;i<=len;i++)
{
if(sum<0)
{
sum=num[i];
}
else
{
sum+=num[i];
}
if(res<sum)
{
res=sum;
}
}
return res;
}
int maxsum2(int num2[][maxn],int n,int m)
{
int b[maxn];
int res2,sum2;
res2=num2[1][1];
sum2=0;
for(int i=1;i<=n;i++)//子矩阵起始行
{
for(int j=1;j<=m;j++)
{
b[j]=0;
}
for(int j=i;j<=n;j++)//子矩阵最后一行
{
for(int k=1;k<=m;k++)
{
b[k]+=a[j][k];//子矩阵每一列的和
}
sum2=maxsum(b,m);//求出从第i行到第j行的最大子矩阵
res2=max(res2,sum2);
}
}
return res2;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
}
}
int ans = maxsum2(a,n,n);
printf("%d\n",ans);
}
return 0;
}
Problem Link:http://acm.hdu.edu.cn/showproblem.php?pid=1559
最大子矩阵
Time Limit: 30000/10000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6133 Accepted Submission(s): 3218
Problem Description
给你一个m×n的整数矩阵,在上面找一个x×y的子矩阵,使子矩阵中所有元素的和最大。
Input
输入数据的第一行为一个正整数T,表示有T组测试数据。每一组测试数据的第一行为四个正整数m,n,x,y(0<m,n<1000 AND 0<x<=m AND 0<y<=n),表示给定的矩形有m行n列。接下来这个矩阵,有m行,每行有n个不大于1000的正整数。
Output
对于每组数据,输出一个整数,表示子矩阵的最大和。
Sample Input
1
4 5 2 2
3 361 649 676 588
992 762 156 993 169
662 34 638 89 543
525 165 254 809 280
Sample Output
2474
AC code:
#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
int a[maxn][maxn];
int n,m,x,y;
/*
int maxsum(int num[],int len)
{
int sum,res;
res=num[1];
sum=0;
for(int i=1;i<=len;i++)
{
if(sum<0)
{
sum=num[i];
}
else
{
sum+=num[i];
}
if(res<sum)
{
res=sum;
}
}
return res;
}
*/
int maxsum(int num[],int len,int y)
{
int sum[maxn];
int res=-99999999;
sum[0]=0;
for(int i=1;i<=len;i++)
{
sum[i]=sum[i-1]+num[i];//前缀和
}
for(int i=1;i+y-1<=len;i++)
{
res=max(res,sum[i+y-1]-sum[i-1]);
}
return res;
}
int maxsum2(int num2[][maxn],int n,int m,int x,int y)
{
int b[maxn];
int res2,sum2;
res2=-99999999;
sum2=0;
for(int i=1;i<=n;i++)//子矩阵起始行
{
for(int j=1;j<=m;j++)
{
b[j]=0;
}
for(int j=i;j<=n;j++)//子矩阵最后一行
{
for(int k=1;k<=m;k++)
{
b[k]+=a[j][k];//子矩阵每一列的和
}
if(j-i+1==x)
{
sum2=maxsum(b,m,y);//求出从第i行到第j行的最大子矩阵
res2=max(res2,sum2);
}
}
}
return res2;
}
int main()
{
// freopen("D:\\in.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d%d",&m,&n,&x,&y);
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
}
}
int ans = maxsum2(a,n,n,x,y);
printf("%d\n",ans);
}
return 0;
}
最大m子段和问题
Problem Link: http://acm.hdu.edu.cn/showproblem.php?pid=1024
Max Sum Plus Plus
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 42065 Accepted Submission(s): 15152
Problem Description
Now I think you have got an AC in Ignatius.L's "Max Sum" problem. To be a brave ACMer, we always challenge ourselves to more difficult problems. Now you are faced with a more difficult problem.
Given a consecutive number sequence S1, S2, S3, S4 ... Sx, ... Sn (1 ≤ x ≤ n ≤ 1,000,000, -32768 ≤ Sx ≤ 32767). We define a function sum(i, j) = Si + ... + Sj (1 ≤ i ≤ j ≤ n).
Now given an integer m (m > 0), your task is to find m pairs of i and j which make sum(i1, j1) + sum(i2, j2) + sum(i3, j3) + ... + sum(im, jm) maximal (ix ≤ iy ≤ jx or ix ≤ jy ≤ jx is not allowed).
But I`m lazy, I don't want to write a special-judge module, so you don't have to output m pairs of i and j, just output the maximal summation of sum(ix, jx)(1 ≤ x ≤ m) instead. ^_^
Input
Each test case will begin with two integers m and n, followed by n integers S1, S2, S3 ... Sn.
Process to the end of file.
Output
Output the maximal summation described above in one line.
Sample Input
1 3 1 2 3
2 6 -1 4 -2 3 -2 3
Sample Output
6 8
解题思路(参考自:https://blog.****.net/winter2121/article/details/72848482):
动态规划,借助矩阵可以直观的看到计算过程。
定义二维数组dp, dp[ i ][ j ],表示前 j 项所构成 i 子段的最大和,且必须包含着第j项,即以第j项结尾
然后是一个递推过程。
求dp[ i ][ j ],有两种情况
1、dp[ i ][ j ] = dp[ i ] [ j-1 ] + a[ j ] ,即把第j项融合到第 j-1 项的子段中,子段数没变
2、dp[ i ][ j ] = dp[ i-1 ] [ t ] + a[ j ],(i-1<= t < j )
把第 j 项作为单独的一个子段,然后找一下i-1个子段时,最大的和,然后加上a[ j ]
然后比较上面两种情况,取大的。
下面看图,红色数字为输入的序列:
如图,要求dp[ 3 ][ 6 ],只需比较他左边的那个,和上面那一行圈起来的之中最大的数,
再加上a[ j ] 即为dp[ 3 ][ 6 ] 的值。
优化一下:
1、沿着第m行的最后一个元素,往左上方向画一条线,线右上方的元素是没必要计算的
那么dp[ i ][ j ] ,j++的时候,j的上限为 i + n - m 即可。
还有左下角那一半矩阵,也是不用计算的,因为1个数字不可能分为2个子段
2、每确定一个dp[ i ][ j ],只需用到本行和上一行,所以不用开维数组也可以,省内存。
开两个一维数组,pre和dp,pre记录上一行,dp记录当前行
3、再对上一行红圈中的数字找最大值时,若用一个循环来找,容易超时。
优化方法:在每次计算dp之前,同时记录下j前面的最大元素。
时间复杂度大致为O(m*n),
通过图片,分析情况1和2,就能发现,从左上角走到第 m 行的最后一个元素即可,找出第 m 行的最大值即为答案。
AC code:
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=1000010;
const int INF=0x3f3f3f3f;
int m,n;
LL a[maxn];
//dp[i][j]=dp[i][j-1]+a[j];//前j-1个数分成i段,a[j]加在第i段上
//dp[i][j]=max(dp[i-1][t])+a[j];(i-1=<t<=j-1) //前j-1个数分成i-1段,a[j]作为单独一段凑成i段
//dp[i][j]=max(dp[i][j-1]+a[j],max(dp[i-1][t])+a[j]) (i-1=<t<=j-1)
/*
int dp[maxn][maxn];
void solve1()
{
for(int i=1;i<=n;i++)
{
dp[0][i]=0;
}
dp[0][0]=0;
for(int i=1;i<=m;i++)
{
for(int j=i;j<=n;j++)
{
if(j>i)//前j-1个数分成i段
dp[i][j]=dp[i][j-1]+a[j];
else
dp[i][j]=-99999999;
int tmp=-99999999;
for(int t=i-1;t<=j-1;t++)//TLE原因
{
tmp=max(tmp,dp[i-1][t]+a[j]);//前t(i-1=<t<=j-1)个数分成i-1段
}
dp[i][j]=max(dp[i][j],tmp);
}
}
printf("%d\n",dp[m][n]);
}
*/
//优化代码(DP滚动数组方法优化,结合画图理解):
LL dp[2][maxn];
void solve2()
{
LL res;
memset(dp,0,sizeof(dp));
for(int i=1,k=1;i<=m;i++,k^=1)
{
LL lastmax,nowmax;
lastmax=-INF;//第i-1行第j列左边所有dp值的最大值
dp[k][i-1]=-INF;//当前第i行第j-1列的dp值(初始时j-1=i-1)
for(int j=i;j<=n;j++)
{
lastmax=max(lastmax,dp[k^1][j-1]);//前j-1个数分成i-1段的最大和(k^1=上一阶段,即上一行第i-1行)
nowmax=dp[k][j-1];//前j-1个数分成i段的最大和(k为当前行,即第i行)
dp[k][j]=max(lastmax,nowmax)+a[j];
}
}
res=-INF;
for(int i=m;i<=n;i++)//找到第m行的最大值,即为答案
{
res=max(res,dp[m&1][i]);//第m行分成了m段,故第一维为 m&1
}
printf("%lld\n",res);
}
int main()
{
while(scanf("%d%d",&m,&n)!=EOF)
{
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
}
//solve();//TLE && MLE
solve2();
}
return 0;
}