首页 > 代码库 > 【算法数据结构Java实现】时间复杂度为O(n)的最大和序列
【算法数据结构Java实现】时间复杂度为O(n)的最大和序列
1.背景
最大序列和问题一直以来是一个比较经典的算法题，看到这个问题，有很多解题的办法。今天看到了一种时间复杂度只为O(n)的解题算法，在这里记录下。
思路很简单，比方说有P1,P2,P3,P4.....这样一个序列，我们从P1开始求和，比如说在P5时求和数小于零，就可以断定。第一种情况，最大序列在P1~P5之间，或者说在P6~Pn之间。因为如果P1+P2+......+P5的和小于零，那么它可以看成一个数，而且是序列第一个数，则任何一个最大序列都不会包含这个数。
2.代码实现
package Algorithm_analysis;
public class MaxSumOfArray {
public static void main(String args[]){
System.out.print(max_sum());
}
public static int max_sum(){
int[] array={-2,11,-4,13,-5,-2};
int max_sum=0;
int array_sum=0;
for(int j=0;j<array.length;j++)
{
array_sum+=array[j];
if(array_sum<0){
max_sum=0;
}
if (array_sum>max_sum)
{
max_sum=array_sum;
}
}
return max_sum;
}
}
参考：http://blog.csdn.net/superchanon/article/details/8228212 （完全四种实现方法）
/********************************
* 本文来自博客 “李博Garvin“
* 转载请标明出处:http://blog.csdn.net/buptgshengod
******************************************/
【算法数据结构Java实现】时间复杂度为O(n)的最大和序列
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。