算法导论——求最大子数组问题-白红宇

算法导论——求最大子数组问题

阅读量：4310 次

发布时间：2019-06-06

本文共 2030 字，大约阅读时间需要 6 分钟。

利用分治算法求最大子数组问题

#include
     
      #include
      
       #define _CRT_SECURE_NO_WARNINGS#pragma warning(disable:4996)int const N = 100;using namespace std;struct ARRAY {    int high;    int low;    int sum;};int A[N];ARRAY FIND_MAX_SUBARRAY(int* A, int low, int high);ARRAY FIND_MAX_CROSSING_SUBARRAY(int* A, int low, int mid, int high);int main() {    int i;    int n=0;    for (i = 1; i <= N-1; i++) {        cin >> A[i];        n++;        char c;//= cin.get();        c = getchar();        if (c != ' ') break;    }    printf("\n");    ARRAY array;    array= FIND_MAX_SUBARRAY(A, 1, n);    for (i = array.low; i <= array.high; i++) {        printf("%d ", A[i]);    }    return 0;}ARRAY FIND_MAX_CROSSING_SUBARRAY(int* A, int low, int mid, int high) {    int left_sum = -999;    int right_sum = -999;    int sum = 0;    int max_left=0,max_right=0;    int i;    for (i = mid; i >= low ; i--) {        sum = sum + A[i];        if (sum > left_sum) {            left_sum = sum;            max_left = i;        }    }    sum = 0;    for (i = mid+1; i <= high; i++) {        sum = sum + A[i];        if (sum > right_sum) {            right_sum = sum;            max_right = i;        }    }    ARRAY p;    p.sum = left_sum + right_sum;    p.low = max_left;    p.high = max_right;    return p;}ARRAY FIND_MAX_SUBARRAY(int* A, int low, int high) {    if (low == high) {        ARRAY p;        p.sum = A[low];        p.low = A[low];        p.high = A[high];        return p;    }    else {        ARRAY cross;        ARRAY left;        ARRAY right;        int mid = (low + high) / 2;        left = FIND_MAX_SUBARRAY(A, low, mid);        right = FIND_MAX_SUBARRAY(A, mid+1, high);        cross = FIND_MAX_CROSSING_SUBARRAY(A, low, mid, high);        if (left.sum >= right.sum && left.sum >= cross.sum) {            return left;        }        else if (left.sum < right.sum && right.sum >= cross.sum) {            return left;        }        else return cross;    }    }

输入输出：