注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

众里寻他千百度,名师成就满分路

AP 微积分 AP 计算机 腾飞的博客

 
 
 

日志

 
 
关于我

大学讲师,中国首批AP计算机教师,著有中国第一套,历经五年实践证明深受学生欢迎的成功的AP计算机双语教材,2013年以93%的满分率开创了中国AP计算机成功的先河,远远超出全美26.6%的满分率,为中国AP计算机教学树立了典范,并在同年加拿大计算机竞赛中勇夺桂冠,任教学生获哥伦比亚大学,麻省理工学院,卡耐基梅隆大学,宾夕法尼亚大学,康奈尔大学,西北大学等学校录取,远程学生遍及北京、长春、南京、重庆、广州、济南, 深圳、成都、费城,洛杉矶,加州,宾州,新罕布什尔州等地,希望借此平台为信息技术的发展做出贡献!

网易考拉推荐

【转载】最大子序列和  

2015-10-29 07:33:02|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
本文转载自追风逐月《最大子序列和》

        1.求一个序列的最大子序列和的算法时间复杂度为O(n^3),即枚举算法,也就是说:将原序列的每个子序列枚举出来并求和,最后从中找出一个最大值,算法如下:

        long maxSubSum(const long  *a) 

       long max = 0; 

       for (int i = 0; i < a.size(); i++) 

       

              for (int j = i; j < a.size(); j++) 

              

                     long sum = 0; 

 

                     for (int k = i; k <= j; k++) 

                     

                            sum += a[k]; 

                     

                     if (sum > max) 

                            max=sum ;

              

       

       return max; 

} 

2. 时间复杂度为O(n^2)。此算法是先在以第i个元素a[i]开始(包含a[i])的子序列中找到一个最大子序列和,然后再从这些最大子序列和中找出最大的一个子序列和,即为原序列的最大子序列和。

    long maxSubSum(const long *a) 

       long max = 0; 

       for (int i = 0; i < a.size(); i++) 

       

              long sum = 0;

              for (int j = i; j < a.size(); j++) 

              {

                        sum += a[j];

                        if(sum > max)

                                 max = sum;  

              } 

       

       return max; 

} 

3. 时间复杂度为O(nlgn)。此算法主要采用了“分治思想”,一个序列的是最大子序列出现的位置只有三种情况:i) 在原序列的最左半部分,ii)在原序列的最右半部分,iii)横跨序列中部的占据序列左右两个部分。前两种情况递归求解,第三种情况的最大和可以通过求出前半部分最大和(包含前半部分最后一个元素)以及后半部分最大和(包含后半部分的第一个元素)相加而得到。

long maxSumRec(const long *a, int l, int r) 

       if (l == r) 

       

              if (a[l] > 0) 

                     return a[l]; 

              else 

                     return 0; 

       

       int center = (l + r) / 2; 

       long maxLeftSum = maxSumRec(a, l, center); 

       long maxRightSum = maxSumRec(a, center+1, r);

       //求出以左边最后一个数字为尾的序列最大值 

       long maxLeftBorderSum = 0, leftBorderSum = 0; 

       for (int i = center; i >= l; i--) 

       

              leftBorderSum += a[i]; 

              if (leftBorderSum > maxLeftBorderSum) 

                     maxLeftBorderSum = leftBorderSum; 

       }

       //求出以右边第一个数字开始的序列最大值 

       long maxRightBorderSum = 0, rightBorderSum = 0; 

       for (int j = center+1; j <= r; j++) 

       

              rightBorderSum += a[j]; 

              if (rightBorderSum > maxRightBorderSum) 

                     maxRightBorderSum = rightBorderSum; 

       

        //返回三者中的最大值

       return max(maxLeftSum, maxRightSum,  

              maxLeftBorderSum + maxRightBorderSum); 

 

long maxSubSum(const long *a) 

       return maxSumRec(a, 0, a.size()-1); 

}

//求出三个long中的最大值 

long max(long a, long b, long c) 

       if (a < b) 

       

              a = b; 

       

       if (a > c) 

              return a; 

       else 

              return c; 

}

4. 时间复杂度为O(n). 此算法是一个线性时间的算法,程序较为简单,但是不容易理解其正确性。简单地说,最大子序列不可能以和为负数的子序列为前缀的。

long maxSubSum(const long *a) 

       long max = 0, sum = 0; 

       for (int j = 0; j < a.size(); j++) 

       

             sum += a[j]; 

              if (sum > max ) 

                     max = sum; 

              else if (sum < 0) 

                     sum = 0; 

       

       return max ; 

}

还有一种算法时间复杂度也是O(n),但是需要额外的空间开销:

long maxSubSum(const long *a) 

       long b[a.size()];

       b[0] = a[0];

       long max = b[0];

       for (int j = 1; j < a.size(); j++) 

       

              b[j] = ((b[j-1] + a[j]) > a[j])? b[j-1] + a[j] : a[j];              

              if (b[j] > max ) 

                     max = b[j]; 

       

       return max ; 

}

  评论这张
 
阅读(89)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017