关于一维模式识别的快速解决方案.

类别:Java 点击:0 评论:0 推荐:

问题原型:给定一个一维向量,向量的值为正数或者负数,我们假定没有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;
  }
}

本文地址:http://com.8s8s.com/it/it13991.htm