最大子序列和（maxSubSeqSum）
- 时间复杂度:T(N)=O(N3)
int MaxSubSeqSum(int arrays[],int length){
int i,j,k,thisSum=0,maxSum=0;
for(i=0;i<length;i++){
for(j=i;j<length;j++){
thisSum=0;
for(k=i;k<=j;k++){
thisSum+=arrays[k];
}
if(thisSum>maxSum)maxSum=thisSum;
};
}
return maxSum;
}
最大子序列和改进1（maxSubSeqSum）
- 时间复杂度:T(N)=O(N2)
int MaxSubSeqSum(int arrays[],int length){
int i,j,thisSum=0,maxSum=0;
for(i=0;i<length;i++){//i是子列左端
thisSum=0;//从arrays[i]到arrays[j]的子序列和
for(j=i;j<length;j++){//j是子序列右端
thisSum+=arrays[j];
if(thisSum>maxSum)maxSum=thisSum;//如果本次求和大于最终结果，更新maxSum
};
}
return maxSum;
}
最大子序列和（maxSubSeqSum）--分治法
算法复杂度:T(N)=O(NlgN)
int MaxSubSeqSum(int arrays[], int left, int right) {
int sum = 0;
if (left == right) {
if (arrays[left] > 0)return arrays[left];
else sum = 0;
} else {
int middle = (left + right) / 2;
int leftSum = MaxSubSeqSum(arrays, left, middle);
int rightSum = MaxSubSeqSum(arrays, middle + 1, right);
int finalLeftSum = 0, thisLeftSum = 0;
for (int i = left; i <=middle; i++) {
thisLeftSum += arrays[i];
if (thisLeftSum > finalLeftSum)finalLeftSum = thisLeftSum;
}
int finalRightSum = 0, thisRightSum = 0;
for (int j = middle + 1; j < right; j++) {
thisRightSum += arrays[j];
if (thisRightSum > finalRightSum)finalRightSum = thisRightSum;
}
sum = finalLeftSum + finalRightSum;
printf("left sum is %d,right sum is %d\n",finalLeftSum,finalRightSum);
if (sum < leftSum)sum = leftSum;
if (sum < rightSum)sum = rightSum;
}
return sum;
}
测试主函数
int main() {
int array[] ={1,6,-5,4,2,-3,6};
int result = MaxSubSeqSum(array,0,7);
printf("result is %d\n", result);
}
运行结果
为了方便观察，我们将每次左右两边求得的最大子序列最大和都打印出来
F:\ClionProject\DataStruct\cmake-build-debug\DataStruct.exe
left sum is 1,right sum is 6
left sum is 0,right sum is 4
left sum is 7,right sum is 0
left sum is 2,right sum is 0
left sum is 6,right sum is 0
left sum is 0,right sum is 6
left sum is 6,right sum is 5
result is 11
Process finished with exit code 0
