最大子段和有关问题,用得上动态规划吗
最大子段和问题,用得上动态规划吗?
在看一本讲算法基础的书. 在动态规划中讲到一个题目叫最大子段和:给定一个整数序列,求其连续子序列
的和的最大值(当然也就等于要求求出和最大的子段)及长度. 如果序列中全为负数则规定最大子段和为0,
长度L=0.
我想的方法很简单:显然最大子段的左右两个数字必定为正数,最左边数字的左邻是负数,最右边数字的右
邻是负数. 因为既然最大子段没有继续向两边延伸必定由于从它两端往两边连续求和时不再出现和为正值
的情况.所以我的方法是从左向右和从右向左分别进行两次遍历,找出最大子段的两个端点:
//设输入序列为a[0..n-1]
int i=n, j=-1, L, sum;
int k=n-1, subsum;
while (a[k] <=0) k--;//找从右往左第一个正数
if (k <0) L=sum=0;//没有一个是正数
else {
while (true) {
i=k;
subsum=0;
while (k> =0 && subsum <=0) {
k--;
subsum+=a[k];
}
if (k <0) break;
}
}
//然后用同样方法从左向右遍历,从而求出j. 最后求出L与sum. 略
但书中讲的思路是动态规划,我没大想明白这道题有什么明显的最优子结构.书里说:
如果将所给序列a[1..n]分为长度相等的前后两段,分别求出这两段的最大子段和,则总序列的最大子段和
有三种情况:
(1)与前段的相同; (2)与后段的相同; (3)跨前后两段.
(1),(2)两种情况可递归求得(这好理解); 而对于(3), "容易看出,a[n/2]与a[n/2+1]在最优子序列中 "
我就不明白为什么了. 而且很明显能举出反例来:
a[1..14]={-3, 2, -1, 4, -5, 2, 1, 2, 3, -4, 5, -6, 7, -8},
容易看出来若分成长为7的前后两段,则前一段的最大和子段是{2,-1,4},后一段的是{2,3,-4,5,-6,7}(或
者只有一个{7},是一样的), 而全序列的则是{2, -1, 4, -5, 2, 1, 2, 3, -4, 5, -6, 7}. 这符合第(3)
情况,然而a[n/2]却不在前一段的最大和子段中.
究竟怎么用动态规划方法考虑才正确呢?
------解决方案--------------------
而对于(3), "容易看出,a[n/2]与a[n/2+1]在最优子序列中 "
-------------------------------------------------
这里是指a[n/2]与a[n/2+1]在全序列的最优子序列中，并不是说a[n/2]与a[n/2+1]就一定都在两个子序列的最优序列中。换句话说，为了在3的情况下得到全序列的最优子序列，你并不是总是可以简单的合并两个最优序列
lz书上描述的方法我也没看到明显的DP的痕迹，不过这是个典型的divide and conquer方法：）
------解决方案--------------------
没看懂怎么找到的端点阿 lz解释解释
------解决方案--------------------
这个问题我好象05年做过，也是发在****上的。现在把我的代码贴出来。
//求一个整型数组（链）里面子链各数和的最大值
#include <iostream.h>
#define MAX_NUM_CNT 100
void main()
{
int data[] = {-1,-2,-234,-588,-2875,-28973,-923748,-293};
int numCount = sizeof(data)/sizeof(int);
int i = numCount - 1;
int dataR[MAX_NUM_CNT];
dataR[i] = data[i]> 0?data[i]:0;
int tmp;
for(;i> 0;--i){
tmp = i-1;
dataR[tmp] = dataR[i] + data[tmp];
if(dataR[tmp] <0)dataR[tmp] = 0;
}
long maxSum = 0,tmpSum = 0;
for(i=0;i <numCount;++i){
if(maxSum <tmpSum+dataR[i]) maxSum = tmpSum+dataR[i];
tmpSum += data[i];
if(tmpSum < 0) tmpSum = 0;
}
cout < < "max: " < <maxSum;
}
在看一本讲算法基础的书. 在动态规划中讲到一个题目叫最大子段和:给定一个整数序列,求其连续子序列
的和的最大值(当然也就等于要求求出和最大的子段)及长度. 如果序列中全为负数则规定最大子段和为0,
长度L=0.
我想的方法很简单:显然最大子段的左右两个数字必定为正数,最左边数字的左邻是负数,最右边数字的右
邻是负数. 因为既然最大子段没有继续向两边延伸必定由于从它两端往两边连续求和时不再出现和为正值
的情况.所以我的方法是从左向右和从右向左分别进行两次遍历,找出最大子段的两个端点:
//设输入序列为a[0..n-1]
int i=n, j=-1, L, sum;
int k=n-1, subsum;
while (a[k] <=0) k--;//找从右往左第一个正数
if (k <0) L=sum=0;//没有一个是正数
else {
while (true) {
i=k;
subsum=0;
while (k> =0 && subsum <=0) {
k--;
subsum+=a[k];
}
if (k <0) break;
}
}
//然后用同样方法从左向右遍历,从而求出j. 最后求出L与sum. 略
但书中讲的思路是动态规划,我没大想明白这道题有什么明显的最优子结构.书里说:
如果将所给序列a[1..n]分为长度相等的前后两段,分别求出这两段的最大子段和,则总序列的最大子段和
有三种情况:
(1)与前段的相同; (2)与后段的相同; (3)跨前后两段.
(1),(2)两种情况可递归求得(这好理解); 而对于(3), "容易看出,a[n/2]与a[n/2+1]在最优子序列中 "
我就不明白为什么了. 而且很明显能举出反例来:
a[1..14]={-3, 2, -1, 4, -5, 2, 1, 2, 3, -4, 5, -6, 7, -8},
容易看出来若分成长为7的前后两段,则前一段的最大和子段是{2,-1,4},后一段的是{2,3,-4,5,-6,7}(或
者只有一个{7},是一样的), 而全序列的则是{2, -1, 4, -5, 2, 1, 2, 3, -4, 5, -6, 7}. 这符合第(3)
情况,然而a[n/2]却不在前一段的最大和子段中.
究竟怎么用动态规划方法考虑才正确呢?
------解决方案--------------------
而对于(3), "容易看出,a[n/2]与a[n/2+1]在最优子序列中 "
-------------------------------------------------
这里是指a[n/2]与a[n/2+1]在全序列的最优子序列中，并不是说a[n/2]与a[n/2+1]就一定都在两个子序列的最优序列中。换句话说，为了在3的情况下得到全序列的最优子序列，你并不是总是可以简单的合并两个最优序列
lz书上描述的方法我也没看到明显的DP的痕迹，不过这是个典型的divide and conquer方法：）
------解决方案--------------------
没看懂怎么找到的端点阿 lz解释解释
------解决方案--------------------
这个问题我好象05年做过，也是发在****上的。现在把我的代码贴出来。
//求一个整型数组（链）里面子链各数和的最大值
#include <iostream.h>
#define MAX_NUM_CNT 100
void main()
{
int data[] = {-1,-2,-234,-588,-2875,-28973,-923748,-293};
int numCount = sizeof(data)/sizeof(int);
int i = numCount - 1;
int dataR[MAX_NUM_CNT];
dataR[i] = data[i]> 0?data[i]:0;
int tmp;
for(;i> 0;--i){
tmp = i-1;
dataR[tmp] = dataR[i] + data[tmp];
if(dataR[tmp] <0)dataR[tmp] = 0;
}
long maxSum = 0,tmpSum = 0;
for(i=0;i <numCount;++i){
if(maxSum <tmpSum+dataR[i]) maxSum = tmpSum+dataR[i];
tmpSum += data[i];
if(tmpSum < 0) tmpSum = 0;
}
cout < < "max: " < <maxSum;
}