最大子段和（顺序求和+比较、分治策略、动态规划）_动态规划算法的顺序求和比较

1.顺序求和+比较

int  MaxSum(int n，int *a，int& besti，int& bestj)
{     int sum=0;
       for (int i = 1; i <= n; i++)
          for (int j = i ; j <= n; j++){
              int thissum=0;
              for (int k = i ; k<=j ; k++) thissum+=a[k];
              if (thissum>sum) {                  
              	  sum=thissum;
                  besti=i ;
                  bestj=j ;  //记录i,j
              }
       }
       return sum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

显然用该方法时间复杂度O(n³)

改进：

int MaxSum(int n, int *a, int &besti, int &bestj)
{   int sum=0;
	for(i=1;i<=n;i++){
	int thissum=0;
	for(j=i;j<=n;j++){  
      thissum+=a[j];
 	if(thissum>sum){ sum=thissum; besti=i;bestj=j;}
	}
	}
	 return sum;
}
1
2
3
4
5
6
7
8
9
10
11

时间复杂度变为O(n²)

2.分治法

int MaxSubSum(int a, int left, int right)
{ int sum=0;
   if (left==right) sum=a[left]>0?a[left]:0;
   else
   {int center=(left+right)/2;
   int leftsum= MaxSubSum(a,left,center);
   int rightsum=MaxSubSum(a,center+1,right);
   int s1=0;lefts=0;
   for (int i=center;i>=left;i--)
   {   lefts+=a[i];
        if (lefts>s1) s1=lefts;
   }
   int s2=0;rights=0;
   for (int i=center+1;i<=right;i++)
   {   rights+=a[i];
        if (rights>s2) s2=rights;
   }
   sum=s1+s2;
    if (sum<leftsum) 
        sum=leftsum;
    if (sum<rightsum) 
        sum=rightsum;
  }
  return sum;
}

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

时间复杂度为O(nlogn)

3.动态规划

int MaxSum(int n, int a)
{
    int sum=0; b=0;
    for (int i=1;i<=n;i++)  
    {
        if (b>0) b+=a[i]; 
        else b=a[i]; 
        if (b>sum) sum=b;
    }
    return sum;
}
1
2
3
4
5
6
7
8
9
10
11

时间：O(n)、空间：O(1)

推广题1：最大子矩阵和

问题描述：给定一个m行n 列的整数矩阵a，试求矩阵a 的一个子矩阵，使其各元素之和为最大。

int MaxSum2(int m, int n, int **a)
{  int sum=0;
    int *b=new int[n+1];
    for (int i=1; i<=m; i++) 
    {   for (int k=1; k<=n; k++) b[k]=0;
   	    for (int j=i; j<=m; j++){
              for (int k=1; k<=n; k++)  b[k]+=a[j][k];
              int max=MaxSum(n,b);
              if (max>sum) sum=max;
          }
     }
    return sum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

结合上一个代码块内容，完整代码：
（法一）

#include<iostream>
using namespace std;
const int N=1e4;
int a[N][N];
int MaxSum(int n,int *c)
{
	int sum=0,b=0;
	int i;
	for(i=1;i<=n;i++){
		if(b>0)b+=c[i];
		else b=c[i];
		if(b>sum)sum=b;
	}	
	return sum;
}
int MaxSum2(int m,int n)
{   int sum=0;
    int *b=new int[n+1];  //动态分配空间，一般大项目工程会用到；这里定义int b[1001]即可（静态分配空间）
    int i,j,k;
    for(i=1;i<=m;i++){
    	for(k=1;k<=n;k++)b[k]=0;
    	for(j=i;j<=m;j++){
    		for(k=1;k<=n;k++)b[k]+=a[j][k];
    		int max=MaxSum(n,b);
    		if(sum<max)sum=max;
		}
	}
    return sum;
}

int main()
{
	int m,n;
	cin>>m>>n;
	int i,j;
	for(i=1;i<=m;i++){
		for(j=1;j<=n;j++){
			cin>>a[i][j];
		}
	}
	cout<<MaxSum2(m,n)<<endl;
}
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

（法二）

#include<iostream>
using namespace std;
int **a;         //仍采用动态分配模式
int MaxSum(int n,int *c)
{
	int sum=0,b=0;
	int i;
	for(i=1;i<=n;i++){
		if(b>0)b+=c[i];
		else b=c[i];
		if(b>sum)sum=b;
	}	
	return sum;
}
int MaxSum2(int m,int n)
{   int sum=0;
    int *b=new int[n+1];
    int i,j,k;
    for(i=1;i<=m;i++){
    	for(k=1;k<=n;k++)b[k]=0;
    	for(j=i;j<=m;j++){
    		for(k=1;k<=n;k++)b[k]+=a[j][k];
    		int max=MaxSum(n,b);
    		if(sum<max)sum=max;
		}
	}
    return sum;
}

int main()
{
	int m,n;
	cin>>m>>n;
	int i,j;
	a=new int*[m+1];       //先定义行
	for(i=1;i<=m;i++)a[i]=new int[n+1];   //再定义列
	for(i=1;i<=m;i++){
		for(j=1;j<=n;j++){
			cin>>a[i][j];
		}
	}
	cout<<MaxSum2(m,n)<<endl;
}
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

推广题2：求最大m子段和
借鉴了别的大佬的代码（现在还有点不明白）：

#include<bits/stdc++.h>
using namespace std;  
typedef long long ll;
const int N=1e4+5; 
const int INF=0x3f3f3f3f;
int n,m;
ll a[N],dp[2][N];   
int main()  
{
    while(cin>>n>>m)
    { 
        for(int i=1;i<=n;i++) 
			scanf("%lld",a+i);  
		for(int i=0;i<=n;i++)
			dp[0][i]=0,dp[1][i]=0;    
		
        for(int i=1,k=1;i<=m;i++,k^=1)    
        {
        	dp[k][i-1]=-INF;   
            ll maxpre=-INF;    
            for(int j=i;j<=n-m+i;j++)
            {
                maxpre=max(maxpre,dp[k^1][j-1]);     
                dp[k][j]=max(dp[k][j-1],maxpre)+a[j]; 
            }
        }
        ll ans=-INF;
        for(int i=m;i<=n;i++)   
            ans=max(ans,dp[m&1][i]);
        printf("%lld\n",ans);
    }  
}
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