給出一個無序數組, 找出連續的任意多個元素, 使得其和加起來是最大的, 要求時間復雜度為 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 閱讀(2490)
評論(3) 編輯 收藏