本文主要是介绍最大子段和（51Nod 1049）、最小正子段和（51Nod 1065）、总结（最小子段和、最大子段和、最小正子段和），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
最大子段和
一.问题描述
给定长度为n的整数序列，a[1...n], 求[1,n]某个子区间[i , j]使得a[i]+…+a[j]和最大.或者求出最大的这个和.例如(-2,11,-4,13,-5,2)的最大子段和为20,所求子区间为[2,4].
二.例题
51Nod 1049
N个整数组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的连续子段和的最大值。当所给的整数均为负数时和为0。
第1行：整数序列的长度N（2 <= N <= 50000) 第2 - N + 1行：N个整数（-10^9 <= A[i] <= 10^9）
输出最大子段和。
6 -2 11 -4 13 -5 -2
20思路：从前往后求和，若当前sum<0，那么sum+a[i]肯定小于a[i]，所以这种情形下加上sum无意义，此时sum设为0.所以从前往后记录下sum最大的时候即可。
代码：
#include<stdio.h>
#include<string.h>
int main()
{int s[51000]; int n;while(~scanf("%d",&n)){for(int i=0;i<n;i++)scanf("%d",&s[i]);long long max=s[0],sum=s[0];for(int i=1;i<n;i++){if(sum<0)sum=0;sum+=s[i];if(sum>max)max=sum;}printf("%lld\n",max);} return 0;
}三. 问题分析
题目简单，上网查一下发现有别人的总结，就记录下来了，尤其分治的思想，真的很值得学习。
1.穷举法
穷举应当是每个人都要学会的一种方式，这里实际上是要穷举所有的[1,n]之间的区间，所以我们用两重循环，可以很轻易地做到遍历所有子区间，一个表示起始位置，一个表示终点位置.代码如下:
int start = 0;//起始位置 int end = 0; //结束位置 int max = 0; for(int i = 1; i <= n; ++i) { for(int j = i; j <= n;++j) { int sum = 0; for(int k = i; k <=j; ++k) sum += a[k]; if(sum > max) { start = i; end = j; max = sum; } } }
这个算法是几乎所有人都能想到的，它所需要的计算时间是O(n^3).当然，这个代码还可以做点优化，实际上我们并不需要每次都重新从起始位置求和加到终点位置.可以充分利用之前的计算结果.
或者我们换一种穷举思路,对于起点 i，我们遍历所有长度为1,2,…,n-i+1的子区间和，以求得和最大的一个.这样也遍历了所有的起点的不同长度的子区间，同时，对于相同起点的不同长度的子区间，可以利用前面的计算结果来计算后面的.
比如，i为起点长度为2的子区间和就等于长度为1的子区间的和+a[i+1]即可，这样就省掉了一个循环，计算时间复杂度减少到了O(n^2).代码如下:
int start = 0;//起始位置
int end = 0;//结束位置
int max = 0;
for(int i = 1; i <= n; ++i)
{ int sum = 0; for(int j = i; j <= n;++j) { sum += a[j]; if(sum > max) { start = i; end = j; max = sum; } }
} 2.分治法
求子区间及最大和，从结构上是非常适合分治法的，因为所有子区间[start, end]只可能有以下三种可能性:
- 在[1, n/2]这个区域内
- 在[n/2+1, n]这个区域内
- 起点位于[1,n/2],终点位于[n/2+1,n]内
以上三种情形的最大者，即为所求. 前两种情形符合子问题递归特性，所以递归可以求出. 对于第三种情形，则需要单独处理. 第三种情形必然包括了n/2和n/2+1两个位置，这样就可以利用第二种穷举的思路求出:
- 以n/2为终点，往左移动扩张，求出和最大的一个left_max
- 以n/2+1为起点，往右移动扩张，求出和最大的一个right_max
- left_max+right_max是第三种情况可能的最大值
示例：
int maxInterval(int *a, int left, int right) { if(right==left) return a[left]>0?a[left]:0; int center = (left+right)/2; //左边区间的最大子段和 int leftMaxInterval = maxInterval(a,left,center); //右边区间的最大子段和 int rightMaxInterval= maxInterval(a,center+1,right); //以下求端点分别位于不同部分的最大子段和 //center开始向左移动 int sum = 0; int left_max = 0; for(int i = center; i >= left; –i) { sum += a[i]; if(sum > left_max) left_max = sum; } //center+1开始向右移动 sum = 0; int right_max = 0; for(int i = center+1; i <= right; ++i) { sum += a[i]; if(sum > right_max) right_max = sum; } int ret = left_max+right_max; if(ret < leftMaxInterval) ret = leftMaxInterval; if(ret < rightMaxInterval) ret = rightMaxInterval; return ret; }
分治法的难点在于第三种情形的理解，这里应该抓住第三种情形的特点，也就是中间有两个定点，然后分别往两个方向扩张，以遍历所有属于第三种情形的子区间，求的最大的一个，如果要求得具体的区间，稍微对上述代码做点修改即可. 分治法的计算时间复杂度为O(nlogn).
3.动态规划法
动态规划的基本原理这里不再赘述，主要讨论这个问题的建模过程和子问题结构.时刻记住一个前提，这里是连续的区间
- 令b[j]表示以位置 j 为终点的所有子区间中和最大的一个
- 子问题:如j为终点的最大子区间包含了位置j-1,则以j-1为终点的最大子区间必然包括在其中
- 如果b[j-1] >0, 那么显然b[j] = b[j-1] + a[j]，用之前最大的一个加上a[j]即可，因为a[j]必须包含
- 如果b[j-1]<=0,那么b[j] = a[j] ,因为既然最大，前面的负数必然不能使你更大
对于这种子问题结构和最优化问题的证明，可以参考算法导论上的“剪切法”，即如果不包括子问题的最优解，把你假设的解粘帖上去，会得出子问题的最优化矛盾.证明如下：
- 令a[x,y]表示a[x]+…+a[y] , y>=x
- 假设以j为终点的最大子区间 [s, j] 包含了j-1这个位置，以j-1为终点的最大子区间[ r, j-1]并不包含其中
- 即假设[r,j-1]不是[s,j]的子区间
- 存在s使得a[s, j-1]+a[j]为以j为终点的最大子段和,这里的 r != s
- 由于[r, j -1]是最优解, 所以a[s,j-1]<a[r, j-1],所以a[s,j-1]+a[j]<a[r, j-1]+a[j]
- 与[s,j]为最优解矛盾.
实例：
int max = 0;
int b[n+1];
int start = 0;
int end = 0;
memset(b,0,n+1);
for(int i = 1; i <= n; ++i) { if(b[i-1]>0) { b[i] = b[i-1]+a[i]; }else{ b[i] = a[i]; } if(b[i]>max) max = b[i]; } 动态规划法的计算时间复杂度为O(n),是最优的解。做几道题加深理解
最直白的LIS题：http://acm.hdu.edu.cn/showproblem.php?pid=1087
最大子段和升级版，最大M段和：http://acm.hdu.edu.cn/showproblem.php?pid=1024
原博客地址：http://blog.csdn.net/niteip/article/details/7444973
最小正子段和
一.例题
51Nod 1065 原题链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1065
题目思路：
a[i]=4,-1,5,-2,-1,2,6,-2 (i=0...n-1)
1.从前往后累加，即从a[0]累加到a[i]得到sum[i]，得sum[i]=4,3,8,6,5,7,13,11。得到的该sum[i]值的意义是从0到i的这个子串中的和。如此我们能简单的想到从j(j=0...n-1)到i的子串遍历求和，该算法时间复杂度为O（n*n），对于该题肯定超时；
2.现在我用一个结构体数组node[i]来存储三个值——标号i、’原值num、累加和sum，然后对sum进行排序。排序后逐个遍历数组node[i],具体过程看代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=50050;
struct Node
{int no;ll num;ll sum;
}node[maxn];
bool cmp(Node a,Node b)
{return (a.sum<b.sum)||(a.sum==b.sum&&a.no<b.no);
}
int main()
{int n;ll sum;scanf("%d",&n);sum=0;for(int i=0;i<n;i++){scanf("%lld",&node[i].num);sum+=node[i].num;node[i].no=i;node[i].sum=sum;}sort(node,node+n,cmp);ll minn=(node[0].num>0?node[0].num:inf);for(int i=1;i<n;i++)//遍历过程{if(node[i].no>node[i-1].no&&node[i].sum>node[i-1].sum)//若i-1的标号小于i的标号，{minn=min(node[i].sum-node[i-1].sum,minn);//取node[i-1].no+1...node[i].no这个子串if(node[i].sum>0)minn=min(node[i].sum,minn);if(node[i].num>0)minn=min(node[i].num,minn);}else{for(int j=i-2;j>=0;j--){if(node[i].no>node[j].no&&node[i].sum>node[j].sum)//从当前位置向前遍历，找到一个标号小于当前元素的{ //若找到的j的sum小于0，原sum减去它肯定比原sum大，minn=min(node[i].sum-node[j].sum,minn); //所以无用，要继续找break;}}if(node[i].sum>0)minn=min(node[i].sum,minn);if(node[i].num>0)minn=min(minn,node[i].num);}}printf("%lld\n",minn);return 0;
}下面来看看大神们总结的：
最小子段和，最大子段和，最小正子段和
最大子段和比较好求解，就是一个dp标记走就可以了，当dp<0,让dp等于当前位，dp大于0就加上当前位就好。
最小子段和就是把所有的元素去相反数，然后在此基础上求一个最大子段和就好。
主要想说的是最小正子段和的求法，是先算前i位的累加和dp[i]，并记录标记为i。
然后对所有的dp[i]进行小到大的排序，然后对两个相连的dp[i]，如果后者的标记大于前者的标记，那么它们的差值是候选答案，然后选取候选答案最小的那个。
PS：注意要在里面加一个标记为-1的，和为0的节点。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
pair<ll,int>sum[55555];
int a[55555];
int main()
{int n,i,j;ll ans;cin>>n;ans=99999999;for(i=1;i<=n;i++) cin>>a[i];for(i=1;i<=n;i++) {sum[i].first=sum[i-1].first+a[i];sum[i].second=i;}sort(sum+1,sum+1+n);if(sum[1].first>0)ans=sum[1].first;for(i=2;i<=n;i++) {if(sum[i].first>0) ans=min(ans,sum[i].first);if(sum[i].second>sum[i-1].second && sum[i].first!=sum[i-1].first) ans=min(ans,sum[i].first-sum[i-1].first);}cout<<ans<<endl;return 0;
}
看大神的代码，哪里有啥罗里吧嗦的东西，自叹不如啊。
总结原址：http://blog.csdn.net/kevin_liu11/article/details/50324101
代码原址：http://blog.csdn.net/h1021456873/article/details/48921101
这篇关于最大子段和（51Nod 1049）、最小正子段和（51Nod 1065）、总结（最小子段和、最大子段和、最小正子段和）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
