- #include <stdio.h>
- #include <conio.h>
- #include <malloc.h>
- void printArr(int *start, int *end);
- long findMaximumSubArray(int *start, int *end, int **pointStart, int **pointEnd);
- int main(int argc, char *argv[]) {
- int arr[] = {13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7};
- int *start = arr,
- *end = arr + sizeof(arr) / sizeof(int);
- long sum = 0;
- int **pointStart = (int **) malloc(sizeof(int *)), **pointEnd = (int **) malloc(sizeof(int *));
- sum = findMaximumSubArray(start, end, pointStart, pointEnd);
- printf("max sum:%ld\\n", sum);
- printf("start index: %d, end index: %d\\n", *pointStart - start, *pointEnd - start - 1);
- printf("result:\\n");
- printArr(*pointStart, *pointEnd);
- free(pointStart);
- free(pointEnd);
- _getch();
- return 0;
- }
- long _findMaxCrossingSubArray(int *start, int*middle, int *end, int **pointStart, int **pointEnd);
- long findMaximumSubArray(int *start, int *end, int **pointStart, int **pointEnd) {
- int *middle = 0;
- long sum = 0,
- leftSum = 0,
- rightSum = 0,
- crossingSum = 0;
- int **leftPointStart = (int **) malloc(sizeof(int *)), **leftPointEnd = (int **) malloc(sizeof(int *)),
- **rightPointStart = (int **) malloc(sizeof(int *)), **rightPointEnd = (int **) malloc(sizeof(int *)),
- **crossingPointStart = (int **) malloc(sizeof(int *)), **crossingPointEnd = (int **) malloc(sizeof(int *));
- if(start + 1 == end) {
- *pointStart = start;
- *pointEnd = end;
- sum = *start;
- } else {
- middle = start + (end - start) / 2;
- *leftPointStart = start;
- *leftPointEnd = middle,
- leftSum = findMaximumSubArray(start, middle, leftPointStart, leftPointEnd);
- *rightPointStart = middle;
- *rightPointEnd = end;
- rightSum = findMaximumSubArray(middle, end, rightPointStart, rightPointEnd);
- *crossingPointStart = start;
- *crossingPointEnd = end;
- crossingSum = _findMaxCrossingSubArray(start, middle, end, crossingPointStart, crossingPointEnd);
- if(leftSum >= rightSum && leftSum >= crossingSum) {
- *pointStart = *leftPointStart;
- *pointEnd = *leftPointEnd;
- sum = leftSum;
- } else if(rightSum >= leftSum && rightSum >= crossingSum) {
- *pointStart = *rightPointStart;
- *pointEnd = *rightPointEnd;
- sum = rightSum;
- } else {
- *pointStart = *crossingPointStart;
- *pointEnd = *crossingPointEnd;
- sum = crossingSum;
- }
- }
- free(leftPointStart);
- free(leftPointEnd);
- free(rightPointStart);
- free(rightPointEnd);
- free(crossingPointStart);
- free(crossingPointEnd);
- return sum;
- }
- long _findMaxCrossingSubArray(int *start, int *middle, int *end, int **pointStart, int **pointEnd) {
- long sum = 0,
- leftSum = 0,
- rightSum = 0;
- int i = 0;
- for(i = 0; start + i != middle; ++i) {
- sum += *(middle - i - 1);
- if(leftSum == 0 || leftSum < sum) {
- leftSum = sum;
- *pointStart = middle - i - 1;
- }
- }
- sum = 0;
- for(i = 0; middle + i != end; ++i) {
- sum += *(middle + i);
- if(rightSum == 0 || rightSum < sum) {
- rightSum = sum;
- *pointEnd = middle + i + 1;
- }
- }
- return leftSum + rightSum;
- }
- void printArr(int *start, int *end) {
- int i = 0;
- for(i = 0; start + i != end; ++i) {
- printf("%d:%d\\n", i, *(start + i));
- }
- }
- //该片段来自于http://www.codesnippet.cn/detail/160520149603.html
来源: http://www.codesnippet.cn/detail/160520149603.html