已知求一组数据连续若干数和的最大值采用分治方法得到...
已知求一组数据连续若干数和的最大值采用分治方法得到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); ——————————完成这里的代码—————————————————— } } 注意为了尽量减少答案的多样性,本次编程代码请通过>而不是 <符号进行数据的比较。按照leftsum,rightsum,crosssum的顺序进行比较。>