《分治原理求最大和的连续子数组》由会员分享，可在线阅读，更多相关《分治原理求最大和的连续子数组（3页珍藏版）》请在金锄头文库上搜索。
1、 /*问题描述：求解一个数组中具有最大和的连续子数组 */ #include #include #include #define INF INT_MIN using namespace std; struct ArrayData int max_left; int max_right; int sum; ; ArrayData* Find_Max_Crossing_SubArray(int *a, int low, int mid, int high); ArrayData* Find_MaxMin_Subarray(int *a, int low, int high); int main()
2、 int *a, size; a = NULL; size = 0; cout size; a = new intsize; cout ai; ArrayData *max; max = new ArrayData; max = Find_MaxMin_Subarray(a, 1, size); cout max_left max_right sum = low - 1; i-) sum += ai; if (sum left_sum) left_sum = sum; max-max_left = i; int right_sum = INF; sum = 0; for (int j = mi
3、d; j right_sum) right_sum = sum; max-max_right = j; max-sum = left_sum + right_sum; return max; ArrayData* Find_MaxMin_Subarray(int *a, int low, int high) if (high = low) ArrayData *minmax = new ArrayData; minmax-max_left = low; minmax-max_right = high; minmax-sum = alow - 1; return minmax; else int
4、 mid = (low + high) / 2; ArrayData*leftminmax = Find_MaxMin_Subarray(a, low, mid); ArrayData*rightminmax = Find_MaxMin_Subarray(a, mid + 1, high); ArrayData*crossminmax = Find_Max_Crossing_SubArray(a, low, mid, high); if (leftminmax-sum = rightminmax-sum & leftminmax-sum = crossminmax-sum) return leftminmax; else if (rightminmax-sum = leftminmax-sum & rightminmax-sum = crossminmax-sum) return rightminmax; else return crossminmax;
