给出一个无序数组, 找出连续的任意多个元素, 使得其和加起来是最大的, 要求时间复杂度为 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 阅读(2481)
评论(3) 编辑 收藏