随笔-126  评论-247  文章-5  trackbacks-0

  
给出一个无序数组, 找出连续的任意多个元素, 使得其和加起来是最大的, 要求时间复杂度为 O(N)

    
//In Java
public static int maxSubSum(int[] array){
    
int sum = 0, max = array[0];
    
for(int i = 0; i < array.length; i++){
        sum 
+= array[i];
        
if(sum > max)
            max 
= sum;
        
if(sum < 0)  //如果 sum < 0, 将 sum 重新置 0
            sum = 0;
    }
    
return max;
}
    

 

   
//In C++
#include <stdio.h>
#include 
<string.h>
#include 
<stdlib.h>
#define length(array) sizeof(array) / sizeof(array[0])

int maxSubSum(int *array, int len){
    
int sum = 0, max = array[0];
    
for(int i = 0; i < len; i++){
        sum 
+= array[i];
        
if(sum > max)
            max 
= sum;
        
if(sum < 0)
            sum 
= 0;
    }
    
return max;
}
   


 



  
posted on 2013-02-07 09:22 fancydeepin 阅读(2486) 评论(3)  编辑  收藏

评论:
# re: 最大连续子串的和[未登录] 2013-02-19 13:43 |
有问题
如 8 -1 8?  回复  更多评论
  
# re: 最大连续子串的和[未登录] 2013-02-19 13:44 |
@幻
不好意思,看错了,激动了  回复  更多评论
  
# re: 最大连续子串的和 2013-04-10 09:35 | dohkoos
if (sum < 0)应该是if (sum < max)
  回复  更多评论
  

只有注册用户登录后才能发表评论。


网站导航: