下午真的很想睡觉，可是上床，下床好几次了，都没睡着，焦虑啊！！可能像我这样刚毕业的人都会这样！工资好像还没发！我问他们，他们说其他人都发了。。。马上又要交房租了，我想对房东说，我已经打到你卡上了，你没收到吗？然后我就去露宿街头。。。我很勇敢，但是我不傻！
给定n个整数（可能为负）组成序列a1,a2,...an，求该序列的最大和子段！这个题目有很多解法！！！
一、穷举法
这种方法很容易想到，就不怎么说明了，直接上代码！
代码如下：
int MaxSum(int n,int *a,int &besti,int& bestj)
{
int sum=0;
int i,j;
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;
} 二、二分法
将数组a[1..n]分成左右的两段a[1..n/2]和a[n/2+1...n]；最大和字段可能落在左子段，可能落在右子段，也可能落在中间，即一部分在左，一部分在右；对于前面两种情况可以直接递归求解，对于最后这种情况，只要从a[n/2]出发，分别累加左子段和得到一个最大值s1，右子段和得到一个最大值s2，s1+s2可得到一个最优值；然后取三者最优！！
代码如下：
int MaxSubSum(int *a,int left,int right)
{
int sum=0;
int j,i;
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;
int lefts=0;
for(i=center;i>=left;i--)
{
lefts+=a[i];
if(lefts>s1)
s1=lefts;
}
int s2=0;
int rights=0;
for(j=center+1;j<=right;j++)
{
rights+=a[j];
if(rights>s2)
s2=rights;
}
sum=s1+s2;
if(sum<leftsum) sum=leftsum;
if(sum<rightsum) sum=rightsum;
}
return sum;
}
其实这个算法先将n大的序列二分置大小为1的序列，然后回溯回去，回溯过程中一直取最优值，实现了信息填充和附带功能！
三、动态规划
这种算法最简单，效率也最高，但是不是很容易理解！好的东西常常很难去解释！
我个人是这么理解的，假设最大序列是从第一个数开始加的一个子序列，那么我们只要从第一个数一直加，取最大的那个值解释最优了！当然这只是假设，最大子序列的初始位置可能会在其他地方，这里就有一个舍弃和，和重新累加的问题，假设从1开始加我们得到一个正和，我们就舍弃（当然在这个过程中我们会一直比较最优值，并把它记录下来），重新累加，显然，无论后面累加得到一个正和或者负和我们都应该把前面那个舍弃的正和加进去；类似的当从1累加得到非正数时，我们就应该把它这段累加和舍弃，重新开始累加！
代码如下：
//求一维数组最大和子段 不考虑数组全为负的情况
int maxsum(int n,int *a)
{
int sum=0,b=0;
int i;
for(i=1;i<=n;i++)
{
if(b>0)
b+=a[i];
else
b=a[i];
if(b>sum) sum=b;
}
return sum;
}
最终其实会得到一幅以数列为轴的点图，最高那个就是最大和字段和！
posted on 2010-09-05 17:29
jince 阅读(566)
评论(2) 编辑 收藏 引用 所属分类:
算法设计与分析