2018-04-24 13:41

# 分治法求最大非连续子序列

• 点赞
• 写回答
• 关注问题
• 收藏
• 邀请回答

#### 1条回答默认 最新

• devmiao 2018-04-24 14:38
已采纳
`````` #include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_N 20

int max3(int, int, int);
int maxSubArrayAns(int []);
int maxSubArray(int [], int, int);

int main(){
int nums[MAX_N];
int i;
srand(time(0));
printf("array: \n");
for(int i = 0; i < MAX_N; i++){
nums[i] = (int)(rand() % (MAX_N * 2) - MAX_N);
printf("%d\t", nums[i]);
}
printf("\n");
printf("The max subsequen sum is %d.\n", maxSubArrayAns(nums));

return 0;
}

int max3(int a, int b, int c){
if(a > b)
return a > c ? a : c;
else
return b > c ? b : c;
}

int maxSubArray(int nums[], int left, int right){
int maxLeftSum, maxRightSum;
int maxLeftBorderSum, maxRightBorderSum;
int leftBorderSum, rightBorderSum;

if(left == right)
if(nums[left] > 0)
return nums[left];
else
return 0;

int mid = (left + right) / 2, i;
maxLeftSum = maxSubArray(nums, left, mid);
maxRightSum = maxSubArray(nums, mid + 1, right);

maxLeftBorderSum = 0, leftBorderSum = 0;
for(i = mid; i >= left; i--){
leftBorderSum += nums[i];
if(leftBorderSum > maxLeftBorderSum)
maxLeftBorderSum = leftBorderSum;
}

maxRightBorderSum = 0, rightBorderSum = 0;
for(i = mid + 1; i <= right; i++){
rightBorderSum += nums[i];
if(rightBorderSum > maxRightBorderSum)
maxRightBorderSum = rightBorderSum;
}

return max3(maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum);
}

int maxSubArrayAns(int nums[]){
return maxSubArray(nums, 0, MAX_N - 1);
}
``````

使用分治法的话，平均时间复杂度为Θ(n lg n)。实际上解决最大子序列问题还有一种更加快速的方法，这种方法的时间复杂度是Θ(n)，是一种线性的算法

`````` int maxSubArrayAns(int nums[]){
int i, thisSum = 0, maxSum = 0;
for(i = 0; i < MAX_N - 1; i++){
thisSum += nums[i];
if(thisSum > maxSum)
maxSum = thisSum;
else if(thisSum < 0)
thisSum = 0;
}

return maxSum;
}
``````
点赞 打赏 评论