最大子數組問題——算法導論

分治法思想

分解：子數組一定被原數組左邊或者右邊包含，或者跨越原數組mid下标。

解決：前兩種完全包含的情況形成子問題遞歸求解，并且縮小了問題規模，後一種是我們要解決的問題。

合并：剩餘的問題是求跨越mid的最大子數組，并且從三種情況中選出和最大的。

另外

算導中僞代碼傳回的是三元組，這裡實作的話用結構體傳回坐标和值。

#include <stdio.h>
#include <limits.h>
typedef struct Node {
    int leftPos;//子數組左下标
    int rightPos;
    int sum;//子數組和
}node;
//找到包含mid下标的最大和數組
node find_max_cross(int arr[], int left, int right, int mid)
{
    int max =  INT_MIN;
    int i = ;
    int leftSum = ;
    int leftPos = mid;
    for (i = mid; i >= left; i--) {
        leftSum += arr[i];
        if (leftSum > max) {
            max = leftSum;
            leftPos = i;
        }
    }
    leftSum = max;

    max = INT_MIN;
    int rightSum = ;
    int rightPos = mid;
    for (i = mid+; i <= right; i++) {
        rightSum += arr[i];
        if (rightSum > max) {
            max = rightSum;
            rightPos = i;
        }
    }
    rightSum = max;
    node tmp = { leftPos, rightPos, leftSum + rightSum };
    return tmp;
}

node find_max_subarr(int arr[], int left, int right)
{
    //問題規模會縮小為隻有一個元素
    if(left == right){
        node tmp;
        tmp.sum = arr[left];
        return tmp;
    }
    //三種情況，完全包含于左/右，跨越中點
    int mid = left + ((right - left) >> );
    node leftNode = find_max_subarr(arr, left, mid);
    node rightNode = find_max_subarr(arr, mid+, right);
    //合并子問題
    node cross = find_max_cross(arr, left, right, mid);
    if (leftNode.sum > cross.sum && leftNode.sum > rightNode.sum) {
        return leftNode;
    }
    else if (rightNode.sum > cross.sum && rightNode.sum > leftNode.sum) {
        return rightNode;
    }
    else{
        return cross;
    }
}

int main()
{
    int arr[] = { -, , -, , -, , , -, -, , -,  };
    int length = sizeof(arr) / sizeof(arr[]);
    node ret = find_max_subarr(arr, , length - );
}