问题原型:给定一个一维向量,向量的值为正数或者负数,我们假定没有0(有0也没所谓,只是没什么意义),问哪一段向量的值和为最大? array arr[0...n] 存在 sum(arr[i]...arr[j]) is max!其中i,j属于[0,n].
1.我尝试解决该问题的方法:
首先,引进两个数据结构:
a.struct Meta{ //记录可操作的某个元素
int val; //从这个位置到下一个Meta的StartPos之间的原向量的值之和
int startpos; //该值对应的原向量段的起始位置.
};
b.struct MaxRec{ //记录某个可能成为最大值的位置和值信息.
int startpos;
int endpos;
int val;
};
c.采用栈或队列的工作方式
d.采用预先格式化的数据信息:+ - + - + -......+ 即,使得可操作的数据信息成正负交替出现的 形式,这样有利于我们对数据的判断.当然第一个数据或者最后一个数据如果是负数的话,肯定是我们 舍弃的对象,这样最后出现的结果将是两端都是正数,格式化的过程就是把相连续的同号数累加在一 起,最终使得出现上面 的交替现象.
2.操作过程:
我们假设一次连续出现的三个值为o,p,q.其中o,q为正数,p为对应的负数的绝对值(相反数,因为一定是负数).
对于o,p,q的不同大小关系可以列出下列情况,采用相对应的处理方式:
a.o<p<q 或 o<q<p :留下q,舍弃o,p.即最大的值一定从q开始.进行下面的重复计算
b.p<o<q 或 p<q<o :a+b+c作为一个整体成为一个Meta进入下一个重复计算.即因为p是最小的,故他 们之和肯定比当中的任何一个正数都大,故如此处理.
c.q<o<p :保存一个可能的最大值,那就是o.然后从q开始进行下面的计算,从q开始以后有 可能出现更大的最大值.但他们已不可能捆在一起,因为o+p<0,对q以后的数据不利,故如此处理,以后 得到更大的值时对最大值进行更新即可.
d.q<p<o :同样o可能成为最大值,保存这个最大值,并且把o+p+q作为一个新的Meta,进入 下一次的计算,之所以让o+p+q进入,是因为o+p>0,他对q来说是有利的,因此这样处理.
上面的四种情况可以总结成三种情况:
一.综合b和d:如果o>p,那么肯定加和,而如果p>q那么o可能时最大值.
二.综合a和c:如果o<p,那么肯定舍弃o,p.而如果q<o,那么o可能成为最大值.
3.之所以使用栈来处理Meta(存放Meta的栈),是因为计算的过程中要合并Meta,这样的话,Meta数组就是动态的,而不是静态的,所以用栈比较合适,虽然栈也是数组,但毕竟抽象.
4.记得处理边界情况,也就是说,你应该处理栈是否已经到顶了,以下已经没有正数了
5.可以考虑算法从两端向中间计算的模式,可能会出现高效率的美事,不过仅供参考.
------------------------------------------------------------------------------
------------------------------------------------------------------------------
其中遇到的问题记录(可以不看):
1.判断两个数是否异号:a*b<0的话异号,a*b>0的话同号,但是乘法是很没效率的,可以设计以下方法:
(a^b&0x80000000) == 0同号,否则异号.
注意:&的优先级比^的要高,所以上式应该写成:(a^b)&0x8000000000 == 0
2.最大值与最小值之间:任何一个最大值加上1都会得到最小值,我们通常所说的位数包括符号位,例如4位整数能表达的范围是-8~7,区间是16为2的4次方,显然最大正数是0111为7,最大负数(绝对值)是0111+1=1000,因为第一个为符号位,因此他是-8,取一个正数的相反数,就是让符号位参加运算:取反+1,当然对于最大的正数取反的话正好是最小的负数,因此负数的绝对值最大永远都比正数最大值多1.
------------------------------------------------------------------------------
------------------------------------------------------------------------------
事实证明我的想法是对的:我用了不到O(2n)的时间解决了这个所谓的立方问题.--O(n3)
代码已经变得非常简单(Java描述):
public class Test {
int[] vec = {31,-41,59,26,-153,58,97,-93,-23,84,-43,108}; //初始数组
int startpos; //第一个正数起始位置
int endpos; //最后一个正数结束位置
/**
* 构造函数
*/
public Test() {
}
/**
* 测试函数
* @param args
*/
public static void main(String[] args) {
Test test = new Test();
Object[] arrMeta = test.prepare(test.vec);
MaxRec mres = test.excute(arrMeta);
System.out.print(mres);
}
/**
*准备数据,把连续的正数或者负数都写在一起
* @param vec
* @return
*/
public Object[] prepare(int[] vec){
ArrayList arrList = new ArrayList();
int conint = Integer.MIN_VALUE;
int sum=0; //当前累加和
/*寻找正确的位置
*/
startpos=0;
endpos=vec.length-1;
while(vec[startpos]<0) startpos++;
while(vec[endpos]<0) endpos--;
/*开始处理
*/
Meta aMeta = new Meta(startpos,0);
for(int i=startpos;i<=endpos;i++){
if(sum==0 || ((sum^vec[i])&conint) == 0) { //同号
sum += vec[i];
}else{
aMeta.value = sum;
arrList.add(aMeta);
aMeta = new Meta(i,0);
sum = 0;
i--;
}
}
aMeta.value = sum; //最后一次数据
arrList.add(aMeta);
return arrList.toArray();
}
/**
* 处理过程,找出最大值的方法
* @param arrMeta
*/
public MaxRec excute(Object[] arrMeta){
//通过我们的prepare处理之后,必然出现正-负-正的元素排列,也就是说,o>0,p<0,q>0
MaxRec mr = new MaxRec(0,0,0);
Meta o;
Meta p;
Meta q;
int i = 0;
while(i<arrMeta.length){ //直到处理完最后一个元素为止
o = (Meta)arrMeta[i];
if(i+1 >= arrMeta.length){ //数组越界处理
p = new Meta(endpos+1,0);
}else{
p = (Meta) arrMeta[i+1];
}
if(i+2 >= arrMeta.length){ //数组越界处理
q = new Meta(endpos+1,0);
}else{
q = (Meta) arrMeta[i+2];
}
// 一.如果o>p,那么肯定加和,而如果p>q那么o可能时最大值.
// 二.如果o<p,那么肯定舍弃o,p.而如果q<o,那么o可能成为最大值.
if(o.value > -p.value){
if(-p.value >= q.value && mr.value < o.value ){
mr.value = o.value;
mr.startpos = o.startpos;
mr.endpos = p.startpos;
}
q.value += o.value+p.value;
q.startpos = o.startpos;
}else{
if(q.value < o.value && mr.value < o.value){
mr.value = o.value;
mr.startpos = o.startpos;
mr.endpos = p.startpos;
}
}
i += 2;
}//while loop
return mr;
}
}
/**
*保存各个节点的类,即正负相间的各个元素.
*/
class Meta{
public int value; //单元值
public int startpos; //单元起始位置(数组中位置)
public Meta(int startpos,int value){
this.value = value;
this.startpos = startpos;
}
public String toString(){
return value+" "+startpos;
}
}
/**
* 保存最大值信息的类.
*/
class MaxRec{
public int startpos; //起始位置(数组中位置)
public int endpos; //终止位置(数组中位置)
public int value; //最大值
public MaxRec(int s,int e,int v){
this.startpos = s;
this.endpos = e;
this.value = v;
}
public String toString(){
return "from "+startpos+" to "+endpos+":max-value="+value;
}
}
