设为首页 - 加入收藏 华夏网 ()- 云主机,资讯,互联网,人工智能,云计算,大赢家论坛,区块链,VR,站长网!
热搜: 平台 google 2019 中国
当前位置: 主页 > 电商 > 正文

lt;数据结构与算法分析gt;读书笔记--最大子序列和问题的求解

发布时间:2021-04-04 00:30 所属栏目:[电商] 来源:网络整理
导读:? 现在我们将要叙述四个算法来求解早先提出的最大子序列和问题。 第一个算法,它只是穷举式地尝试所有的可能。for循环中的循环变量反映了Java中数组从0开始而不是从1开始这样一个事实。还有,本算法并不计算实际的子序列;实际的计算还要添加一些额外的代码

?

现在我们将要叙述四个算法来求解早先提出的最大子序列和问题。

第一个算法,它只是穷举式地尝试所有的可能。for循环中的循环变量反映了Java中数组从0开始而不是从1开始这样一个事实。还有,本算法并不计算实际的子序列;实际的计算还要添加一些额外的代码。

    public static int maxSubSum1(int[] a) {
        
        int maxSum = 0;
        
        for(int i = 0;i<a.length;i++)
            int j = i;j<a.length;j++) {
                int thisSum = 0;
                
                int k = i;k<=j;k++)
                    thisSum +=a[k];
                if(thisSum > maxSum)
                    maxSum = thisSum;
            }
    
       return maxSum;
    }
    

?

该算法肯定会正确运行(这用不着花太多时间去证明)。运行时间为O(N的3次方),这完全取决这两行代码:

     )
                    thisSum +=a[k];

?

它们由一个含于三种嵌套for循环中的O(1)语句组成。

下面这行代码循环大小为N

        int i = 0;i<a.length;i++)

?

第二个循环大小为N-i,它可能要小,但也可能是N。我们必须假设最坏的情况,而这可能会使得最终的界有些大。第三个循环的大小为j-i+1我们也要假设它的大小为N。因此总数为

O(1.N.N.N)=O(N的3次方)。

而下面这行代码,开销只是O(1)

 int maxSum = 0;

?

然而,下面这段代码也只不过总共开销O(N的2次方),因为它们只是两层循环内部的简单表达式

         maxSum)
                    maxSum = thisSum;

?

?

第二个算法显然是O(N的2次方)

 int maxSubSum2( [] a) {
       
       ;
       
       ) {
           
           ;
           
           for (int j = 0; j < a.length; j++) {
            
               thisSum += a[j];
               
                maxSum)
                   maxSum = thisSum;
           }
           
       }
       
       
        maxSum;
       
   }
    

?

对这个问题有一个递归和相对复杂的O(N logN)解法,我们现在就来描述它。要是真的没出现O(N)(线性的)解法,这个算法就会是体现递归威力的极好的范例。该方法采用一种对它们求解,这是“分”的部分。“治”阶段将两个子问题的解修补到一起并可能再做些少量的附加工作,最后得到整个问题的解。

在我们的例子中,最大子序列和可能在三处出现。或者整个出现在输入数据的左半部,或者整个出现在右半部,或者跨越输入数据的中部从而位于左右两半部分之中。前两种情况可以递归求解。第三种情况的最大和可以通过求出前半部分(包含前半部分最后一个元素)的最大和以及后半部分(包含后半部分第一个元素)的最大和而得到。此时将这两个和相加。作为一个例子,考虑下列输入,如图:

lt;数据结构与算法分析gt;读书笔记--最大子序列和问题的求解

?

其中前半部分的最大子序列和为6(从元素A1到元素A3)而后半部分的最大子序列和为8(从元素A6到A7)。

前半部分包含其最后一个元素的最大和子序列和是4(从元素A1到元素A4),而后半部分 包含其第一个元素的最大和是7(从元素A5到A7)。因此,横跨这部分且通过中间的最大和为4+7=11(从元素A1到A7)。

我们看到,在形成本例中的最大和子序列的三种方式中,最好的方式是包含两部分的元素。于是,答案为11。

?

有必要对算法3的程序进行一些说明。递归过程调用的一般形式是传递输入的数组以及左边界和右边界,它们界定了数组要被处理的部分。单行驱动程序通过传递数组以及边界0和N-1而将该过程启动。

?

代码示例如下:

package cn.simple.example;

class AlgorithmTestExample {

     maxSum;
    }


    maxSum;
       
   }
    
   
   private int maxSumRec(int [] a,int left,1)"> right) {
       
       if(left == right)
           
           if(a[left] > 0)
                a[left];
           else
               return 0;
       
       
       int center = (left + right)/2;
       int maxLeftSum = maxSumRec(a,left,center);
       int maxRightSum = maxSumRec(a,center+1,right);
       
       int maxLeftBorderSum = 0,leftBorderSum = 0int i = center;i>=left;i--) {
           leftBorderSum +=a[i];
           if(leftBorderSum > maxLeftBorderSum)
               maxLeftBorderSum = leftBorderSum;           
       }
       
       int maxRightBorderSum = 0,rightBorderSum = 0int i = center+1;i<=right;i++) {
        rightBorderSum += a[i];
        
        if(rightBorderSum > maxRightBorderSum)
            
            maxRightBorderSum = rightBorderSum;
       }
       
       return max3(maxLeftSum,maxRightSum,maxLeftBorderSum + maxRightBorderSum);
   }
   
   int max3(int maxLeftSum,1)">int maxRightSum,1)"> i) {
       
     max;
    
    if(maxLeftSum > maxRightSum)
        max = maxLeftSum;
    
    else
        max = maxRightSum;
    
    if(i > max)
        
        max = i;
    
     max;
    
   }


int maxSubSum3(return maxSumRec(a,a.length-1);
   }
    
}

?

看这段代码,如下所示:

 ;
       

?

如果left==right,那么只有一个元素,并且当该元素非负时它就是最大子序列。left>right的情况是不可能出现的,除非N是负数(不过,程序中小的扰动有可能致使这种混乱产生)。

?

下面这两个递归调用,我们可以看到,递归调用总是对小于原问题的问题进行,不过程序小的扰动有可能破坏这个特性。

       

?

我们再看这下面两段代码:

代码1

     leftBorderSum;           
       }

?

代码2

 rightBorderSum;
       }

?

这两段代码达到中间分界处的两个最大和的和数。这两个值的和为扩展到左右两部分的最大和。例程max3返回这三个可能的最大和的最大者。

?

【免责声明】本站内容转载自互联网,其相关言论仅代表作者个人观点绝非权威,不代表本站立场。如您发现内容存在版权问题,请提交相关链接至邮箱:bqsm@foxmail.com,我们将及时予以处理。

网友评论
推荐文章