问题
给定N个整数序列
求函数
的最大值。
算法一
算出所有可能的连续子列的和,并比较
public int MaximumSubsequenceSum1(int[] array,int size) {
int maxSum=0;
int tempSum=0;
for(int i=0;i<size;i++) {
for(int j=i;j<size;j++) {
for(int k=i;k<=j;k++) {
tempSum+=array[k];
}
if(tempSum>maxSum) {
maxSum=tempSum;
}
}
}
return maxSum;
}
时间复杂度O(N^3)
算法二
在解法一的基础上进行改进
public static int MaximumSubsequenceSum2(int[] array,int size) {
int maxSum=0;
int tempSum=0;
for(int i=0;i<size;i++) {
tempSum=0;
for(int j=i;j<size;j++) {
tempSum+=array[j];
if(tempSum>maxSum) {
maxSum=tempSum;
}
}
}
return maxSum;
}
时间复杂度O(N^2)
算法三
递归计算:将数组分为两部分,分别计算左、右和包含左右两边元素的三个最大子列和。
public static int MaximumSubsequenceSum3(int[] array,int size) {
return MaximumSubsequenceSum3Recursion(array,0,size-1);
}
public static int MaximumSubsequenceSum3Recursion(int[] array,int leftIndex,int rightIndex) {
int maxLeftSum;
int maxRightSum;
int maxLeftBorderSum;
int maxRightBorderSum;
int tempLeftBorderSum;
int tempRightBorderSum;
int centerIndex;
//传入数组只有一个数时终止
if(leftIndex==rightIndex) {
return (array[leftIndex]>=0)? array[leftIndex]:0;
}
//分
centerIndex=(leftIndex+rightIndex)/2;
maxLeftSum=MaximumSubsequenceSum3Recursion(array,leftIndex,centerIndex);
maxRightSum=MaximumSubsequenceSum3Recursion(array, centerIndex+1, rightIndex);
//子列元素在左右两边存在的情况
maxLeftBorderSum=0;
tempLeftBorderSum=0;
for(int i=centerIndex;i>=leftIndex;i--) {
tempLeftBorderSum+=array[i];
if(tempLeftBorderSum>maxLeftBorderSum) {
maxLeftBorderSum=tempLeftBorderSum;
}
}
maxRightBorderSum=0;
tempRightBorderSum=0;
for(int i=centerIndex;i<=leftIndex;i++) {
tempRightBorderSum+=array[i];
if(tempRightBorderSum>maxRightBorderSum) {
maxRightBorderSum=tempRightBorderSum;
}
}
return Math.max(maxLeftSum, Math.max(maxRightSum, maxLeftBorderSum+maxRightBorderSum));
}
时间复杂度O(NlogN)。由于是递归计算,所以空间复杂度较大
算法四(在线处理)
public static int MaximumSubsequenceSum3(int[] array,int size) {
int maxSum=0;
int tempSum=0;
for(int i=0;i<size;i++) {
tempSum+=array[i];
if(tempSum>maxSum) {
maxSum=tempSum;
}else if(tempSum<0) {
tempSum=0;
}
}
return maxSum;
}
时间复杂度O(N)
网友评论