所有问题分类1310人阅读
算法（11）
1、问题：求不连续数列的最大和。
2、解释：不连续是指两个数在原始数列中必须是间隔的，比如对原始数列{ 1,2，3,4,5 }，其不连续数列的最大和为9，对应的不连续数列为{1,3,5}，注意1、3是间隔的，3、5也是间隔的。
3、分析：设原始数列为a，当前（待求）的最优解是s[i]，则对当前位置i，分两种情况：
（1）&&& 如果满足条件的数列中无该数a[i]，则s[i]=s[i-1];
（2）&&& 如果满足条件的数列中有该数a[i]，则s[i]=max(a[i],s[i-2],a[i]+s[i-2])
注：对（1），因为最优解中无当前数a[i]，则a[i]前面的所有数的最优，即s[i-1]；
对（2），因为最优解中有当前数a[i],而要求最优解的数列是不连续的，则a[i]的前一个数必须不能要，只能看a[i]往前的第2个数的最优解（s[i-2]），则相当于从2个数s[i-2],a[i]中选择0－2个数，组成最大和(要考虑数值的正负性,比如如果s[i-2]&0,a[i]&0，则当前最优解为s[i]=a[i],即只有当前的一个数。因为前面的最优解s[i-2]为负，a[i]加上s[i-2]后反而小，不是最优解)，即为max (a[i],s[i-2],a[i]+s[i-2]).
4、我自己在考虑这个题目时，没有用数组s[i]，只用{无、有、最优}这3个变量（设分别为no、yes、best，分别对应无当前值a[i]、有当前值a[i]、最后的最优解(相当于求max)，且这3个变量的初始值全为0。
3中分析的2种情况相当于是：
（1）&&& 如无该数a[i]，则no= (前一个best);
（2）&&& 如有该数a[i]，则yes= max(a[i],a[i]+ (前一个no));
（3）&&& best=max(no, yes).
当前的no的值等于前一个best的值（因为无当前数a[i]，故此时最优解是前一个的是优解）；当前的yes的值等于前一个no，再加上当前值a[i]（因为有当前值a[i]，前一个值a[i-1]不能有（即为前一个的no））；当前的best为当前no和yes的最大值，即max(no,yes)。这3个值与上面分析中讲的其实是一样的，因为前一个no就等于s[i-2]，而且yes的值等于当前a[i]加上当前值往前数第二个数的最优解s[i-2]，注意yes值可能为负，但由于no、yes、best的初始值全为0，故总有no
&=0，也有best=max(no,yes) &=0，表明如果原始数列全为负，则表示一个数都不选，如果题目要求必须选的话，则只需选数列a中最大的一个负数即可。
举例如下：对原始数组a{ -12, -20, 80, -36, 50, 90, 43, 1 }，最优解是173＝{80, 50, 43}。计算过程如下：
注：顺序是从左到右，从上到下。表格中130={80,50}表示此时和为130，数列为{80,50}
{80,50,43}
{80,50,43}
{80,50,43}
{80,50,43}
5、参考源代码如下：
#include &stdafx.h&
#include &iostream&
int _tmain(int argc, _TCHAR* argv[])
&&& int aiData[]={ -12,&&&&&& -20,&&&&& 80,&&&&& -36,&&&&& 50,&&&&& 90,&&&&& 43,&&&& 1 };//原始数组
&&& int iNum= 8;//原始数组的元素个数
&&& int iMax_no, iMax_has, iMax_
&&& iMax_no= iMax_has= iMax_best= 0;//no,yes,best初始值全为0
&&& int iT
&&& for ( int i= 0; i& iN ++i)//从前往后一次遍历
&&&&&& iTemp= iMax_//保存没有前一个数时的最优解（即s[i-2]）
&&&&&& iMax_no= iMax_//无当前值a[i](即s[i-1])
&&&&&& iMax_has= iTemp+ aiData[ i];//有当前值a[i](即s[i-2]+a[i])
&&&&&& iMax_best= iMax_no& iMax_has? iMax_no: iMax_// best=max(no,yes)
&&& cout&& &最大间断子序列和为: &&& iMax_best&&&&&
&&& system(&pause&);
&&& return 0;
如果想输出满足条件的数列的所有值，参考以下代码：
（注意，在前面加上#include &vector&）
int aiData[]={& -12,&&&&&& -20,&&&&& 80,&&&&& -36,&&&&& 50,&&&&& 90,&&&&& 43,&&&& 1};//原始数组
&&& int iNum= 8; //原始数组的元素个数
&&& int iMax_no, iMax_has, iMax_
&&& iMax_no= iMax_has= iMax_best= 0; //no,yes,best初始值全为0
&&& vector& int& vbIndex_no, vbIndex_best, vbIndex_//数列向量，以便输//出
&&& int iT
&&& for ( int i= 0; i& iN ++i)
&&&&&& iTemp= iMax_ //保存没有前一个数时的最优解（即s[i-2]）
&&&&&& iMax_no= iMax_ //无当前值a[i](即s[i-1])
&&&&&& iMax_has= iTemp+ aiData[ i]; //有当前值a[i](即s[i-2]+a[i])
&&&&&& vbIndex_temp= vbIndex_//保存没有前一个数时的最优解（即s[i-2]）//时对应的向量
&&&&&& vbIndex_no= vbIndex_//无当前值a[i](即s[i-1]) 时对应的向量
&&&&&& if ( iMax_no&= iMax_has)
&&&&&&&&&& iMax_best= iMax_// best=max(no,yes)&&&&&&&
&&&&&& else
&&&&&&&&&& iMax_best= iMax_// best=max(no,yes)
&&&&&&&&&& vbIndex_best= vbIndex_//没有前一个数时的最优解（即s[i-2]）//时对应的向量
&&&&&&&&&& vbIndex_best.push_back( i);//向量中加上当前值
&&& cout&& &最大间断子序列和为: &&& iMax_best/*&& endl*/;
&&& cout&&&=\t&;
&&& for ( int i= 0; i& ( int)vbIndex_best.size(); ++i)
&&&&&& cout && aiData[ vbIndex_best[ i]]&&&\t&;
&&& cout&&
6、下面看“最大连续子序列和”的问题，与“不连续数列的最大和”的分析大同小异：
(1) 不连续数列的最大和：
&1&如无该数a[i]，则no= ((前一个best);
&2&如有该数a[i]，则yes= max(a[i],a[i]+ (前一个no));
&3&best=max(no, yes).
(2) 最大连续子序列和：
&1&如无该数a[i]，则no=((前一个best);
&2&如有该数a[i]，则yes= max(a[i],a[i]+ (前一个yes));
&3& best=max(no, yes).
比较发现，唯一的区别是yes的值：第1个与(前一个no)有关，第2个与(前一个yes)有关。第1个因为是不连续的，所以不能有前一个；而第2个因为是连续的，所以必须有前一个。
“最大连续子序列和”的参考代码如下（与“不连续数列的最大和”很相似，只有一行红色标注的不同）：
#include &stdafx.h&
#include &iostream&
int _tmain(int argc, _TCHAR* argv[])
&&& int aiData[]={ -12,&&&&&& -20,&&&&& 80,&&&&& -36,&&&&& 50,&&&&& 90,&&&&& 43,&&&& 1 };//原始数组
&&& int iNum= 8;//原始数组的元素个数
&&& int iMax_no, iMax_has, iMax_
&&& iMax_no= iMax_has= iMax_best= 0;//no,yes,best初始值全为
&&& for ( int i= 0; i& iN ++i)//从前往后一次遍历
&&&&&& iMax_no= iMax_//无当前值:no=((前一个best)
&&&&&& iMax_has= aiData[ i]+ ( iMax_has&0? iMax_has: 0);//有当前值:yes= max(a[i],a[i]+ (前一个yes))
&&&&&& iMax_best= iMax_no& iMax_has? iMax_no: iMax_// best=max(no, yes)&
&&& cout&& &最大不连续子序列和为: &&& iMax_best&&
&&& system(&pause&);
&&& return 0;
注：“最大连续子序列和”，与“不连续数列的最大和”很相似，只是间隔的个数不一样（“最大连续子序列和”的2数之间的间隔为0；“不连续数列的最大和” 的2数之间的间隔大于等于1）。
7、扩展：前面的“不连续数列的最大和”问题其实是另一个问题BadNeighbors - 2004 TCCC Round 4的基础，BadNeighbors题目如下：n个数围成一个圆圈，求最大的子集和使得每一个数都不和其他任何数是相邻的。
分析：这其实相当于求前n-1个数和后n-1个数的不连续数列的最大和，（设数组索引从0开始）即a[0-&n-2]、a[1-&n-1]这2个数组的不连续数列的最大和（这样必不会出现首尾相连的情况，满足条件），即求2次前面讲的不连续数列的最大和即可，并取其中较大者为答案。
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：608093次
积分：7013
积分：7013
排名：第3168名
原创：107篇
转载：23篇
评论：68条
(5)(1)(2)(6)(2)(1)(3)(4)(5)(2)(7)(9)(1)(5)(2)(3)(3)(2)(1)(5)(2)(11)(2)(2)(6)(11)(5)(5)(7)(1)(5)(1)(2)(1)在如下表格中.每格填上一个数字后.使每一横行成等差数列.每一纵列成等比数列.则a+b+c的值为( )120.51abcA．1B．2C．3D．98——精英家教网——
暑假天气热？在家里学北京名师课程，
& 题目详情
在如下表格中，每格填上一个数字后，使每一横行成等差数列，每一纵列成等比数列，则a+b+c的值为（　　）120.51abcA．1B．2C．3D．98
科目：高中数学
在如下表格中，每格填上一个数字后，使每一横行成等差数列，每一纵列成等比数列，则a+b+c的值为（　　）
cA．1B．2C．3D．98
科目：高中数学
来源：不详
题型：单选题
在如下表格中，每格填上一个数字后，使每一横行成等差数列，每一纵列成等比数列，则a+b+c的值为（　　）
cA．1B．2C．3D．98
科目：高中数学
来源：不详
题型：单选题
在如下表格中，每格填上一个数字后，使每一横行成等差数列，每一纵列成等比数列，则a+b+c的值为（　　）
cA．1B．2C．3D．98
科目：高中数学
来源：学年河南省三门峡市陕州中学高二（上）第一次月考数学试卷（解析版）
题型：选择题
在如下表格中，每格填上一个数字后，使每一横行成等差数列，每一纵列成等比数列，则a+b+c的值为（ ）120.51abcA．1B．2C．3D．
科目：高中数学
来源：《2.5 等比数列的前n项和》2013年同步练习（2）（解析版）
题型：选择题
在如下表格中，每格填上一个数字后，使每一横行成等差数列，每一纵列成等比数列，则a+b+c的值为（ ）120.51abcA．1B．2C．3D．
科目：高中数学
在如下图的表格中，每格填上一个数字后，使每一横行成等差数列，每一纵行成等比数列，则a+b+c的值为(&&& )A.1&&&&&&&&&&&&&&&&&&&&&&&& B.2&&&&&&&&&&&&&&&&&&& C.3&&&&&&&&&&&&&& D.4
科目：高中数学
填空题 已知数列为等差数列，为其前项和&&&&&&&&&
函数的反函数为，则&&&& 。 已知球O的表面上四点A、B、C、D，平面ABC，ABBC，DA=AB=BC=，则球O的体积等于&&&&&&&& 。 某校在2010年的“八校第一次联考”中有1000人参加考试，数学考试的成绩（，试卷满分150分），统计结果显示数学考试成绩在70分到110分之间的人数约为总人数的，则此次数学考试成绩不低于110分的学生约有&&&&& 人。 有一种数学推理游戏，游戏规则如下：
①在9×9的九宫格子中，分成9个3×3的小九格，用1到9这9个数填满整个格子； ②每一行与每一列都有1到9的数字，每个小九宫格里也有1到9的数字，并且一个数字在每 行每列及每个小九宫格里只能出现一次，既不能重复也不能少，那么A处应填入的数字为&&&&&&&&&& ；B处应填入的数字为&& &&&&&。
科目：高中数学
来源：北京期末题
题型：单选题
将l，2，3，4，5，6，7，8，9这9个数字填在如图的9个空格中，要求每一行从左到右、每一列从上到下分别依次增大，当3，4固定在图中的位置时，填写表格的方法共有
[&&&& ]A．12种B．10种C．8种 D．6种
科目：高中数学
来源：北京五中学年度第一学期期中考试试卷高三数学(理科)
在如下图的表格中，每格填上一个数字，使每一横行成等差数列，每一纵列成等比数列，则a＋b＋c＝________
科目：高中数学
来源：北京五中学年度第一学期期中考试试卷高三数学(文科)
在如下图的表格中，每格填上一个数字，使每一横行成等差数列，每一纵列成等比数列，则a＋b＋c＝________
精英家教网新版app上线啦！用app只需扫描书本条形码就能找到作业，家长给孩子检查作业更省心，同学们作业对答案更方便，扫描上方二维码立刻安装！
请输入姓名
请输入手机号}