答案及解析：[单选题]已知求一组数据连续若干数和的最大值采用分治方法得到O(nlogn)的时间复杂度，请完成下面分治法求解的代码： /*******************************************

问题：

[单选题]已知求一组数据连续若干数和的最大值采用分治方法得到O(nlogn)的时间复杂度，请完成下面分治法求解的代码：
/************************************************************************/
/*    分治法
     最大和子数组有三种情况：
     1)A[1...mid]
     2)A[mid+1...N]
     3)A[i..mid..j]
/************************************************************************/
//find max crossing left and right
int Find_Max_Crossing_Subarray(int arr[], int low, int mid, int high)
{
     const int infinite = -9999;
     int left_sum = infinite;
     int right_sum = infinite;

     int max_left = -1, max_right = -1;

     int sum = 0; //from mid to left;
     for (int i = mid; i >= low; i --) {
         sum += arr[i];
         if (sum > left_sum) {
             left_sum = sum;
             max_left = i;
         }
     }
     sum = 0; //from mid to right
     for (int j = mid + 1; j <= high; j ++) {
         sum += arr[j];
         if (sum > right_sum) {
             right_sum = sum;
             max_right = j;
        }
     }
     return (left_sum + right_sum);
}

int Find_Maximum_Subarray(int arr[], int low, int high)
{
     if (high == low) //only one element;
         return arr[low];
     else {
         int mid = (low + high)/2;
         int leftSum = Find_Maximum_Subarray(arr, low, mid);
         int rightSum = Find_Maximum_Subarray(arr, mid+1, high);
         int crossSum = Find_Max_Crossing_Subarray(arr, low, mid, high);

        ——————————完成这里的代码——————————————————
     }
}

A.if(leftSum>rightSum && leftSum>crossSum） return leftSum;
if(rightSum>leftSum && rightSum>crossSum) return rightSum;
if(crossSum>leftSum && crossSum>rightSum)return crossSum;
B.if(leftSum>rightSum)
{
if(leftSum>crossSum)return leftSum;
else return crossSum;
}
else
{
if(rightSum>crossSum)return rightSum;
else return crossSum;
}
C.if(leftSum>rightSum>crossSum） return leftSum;
else if(rightSum>leftSum>crossSum) return rightSum;
else if(crossSum>leftSum>rightSum)return crossSum;
D.if(leftSum>rightSum>crossSum） return leftSum;
if(rightSum>leftSum>crossSum) return rightSum;
if(crossSum>leftSum>rightSum)return crossSum;

Tags：中国大学MOOC(慕课)电子科技大学数据结构与算法单元测验题答案

答案解析：

╋纠错

您可能感兴趣的问题