最大子序列和（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
