分治法 2

最大字数组问题

暴力解法

typedef struct {
    int leftIndex;
    int rightIndex;
    int maxSum;
} SubArrayData;

void maxSubArraySimple(int array[], int length, SubArrayData *subArrayData){
    int i =0;
    int j = 0;
    int currentSum = array[0];
    
    subArrayData->leftIndex = 0;
    subArrayData->rightIndex = 0;
    subArrayData->maxSum = array[0];
    
    for (i = 0; i < length; ++i){
        currentSum = 0;
        for (j = i; j < length; ++j){
            currentSum += array[j];
            if (currentSum > subArrayData->maxSum){
                subArrayData->leftIndex = i;
                subArrayData->rightIndex = j;
                subArrayData->maxSum = currentSum;
            }
        }
    }
}

算法基本过程：
遍历数组元素，以每一个数组元素为最大子数组第一个元素寻找子数组。

时间复杂度为 n^2

递归解法

typedef struct {
    int leftIndex;
    int rightIndex;
    int maxSum;
} SubArrayData;

void maxMidSubArray(int array[], int lowIndex, int highIndex, int midIndex, SubArrayData *subArrayData){
    int i = 0;
    int currentSum = 0;
    int leftMaxSum = array[midIndex];
    int rightMaxSum = array[midIndex + 1];
    subArrayData->leftIndex = midIndex;
    subArrayData->rightIndex = midIndex + 1;
    subArrayData->maxSum = array[midIndex];
    
    currentSum = 0;
    for (i = midIndex; i >= lowIndex; --i){
        currentSum += array[i];
        if (currentSum > leftMaxSum){
            leftMaxSum = currentSum;
            subArrayData->leftIndex = i;
        }
    }
    
    currentSum = 0;
    for (i = midIndex + 1; i <= highIndex; ++i){
        currentSum += array[i];
        if (currentSum > rightMaxSum){
            rightMaxSum = currentSum;
            subArrayData->rightIndex = i;
        }
    }
    
    subArrayData->maxSum = leftMaxSum + rightMaxSum;
}

void maxSubArray(int array[], int lowIndex, int highIndex, SubArrayData *subArrayData){
    int midIndex = 0;   
    SubArrayData rightMaxSubArrayData;
    SubArrayData midMaxSubArrayData;
    if (lowIndex < highIndex){
        midIndex = (lowIndex + highIndex) / 2;
        maxSubArray(array, lowIndex, midIndex, subArrayData);
        maxSubArray(array, midIndex + 1, highIndex, &rightMaxSubArrayData);
        maxMidSubArray(array, lowIndex, highIndex, midIndex, &midMaxSubArrayData);
        if (subArrayData->maxSum < rightMaxSubArrayData.maxSum){
            (*subArrayData) = rightMaxSubArrayData;
        }
        if (subArrayData->maxSum < midMaxSubArrayData.maxSum){
            (*subArrayData) = midMaxSubArrayData;
        }
    }else if (lowIndex == highIndex){
        subArrayData->leftIndex = lowIndex;
        subArrayData->rightIndex = lowIndex;
        subArrayData->maxSum = array[lowIndex];
    }

}

算法基本过程：
将待处理数组在中点分隔成两个子数组，最大子数组只可能在三个位置出现：

1 左边的子数组

2 右边的子数组

3 跨越中点的子数组

递归的查找这三个最大子数组，返回三者中最大的。

时间复杂度 nlg(n)

习题 4.1-5

时间复杂度 n^2

typedef struct {
    int leftIndex;
    int rightIndex;
    int maxSum;
} SubArrayData;

void question4_1_5(int array[], int length, SubArrayData *subArrayData){
    int i = 0;
    int j = 0;
    int leftMaxSum = 0;
    int rightMaxSum = 0;

    subArrayData->leftIndex = 0;
    subArrayData->rightIndex = 0;
    subArrayData->maxSum = array[0];

    for (i = 0; i < length - 1; ++i){
        leftMaxSum += array[i];
        if (leftMaxSum > subArrayData->maxSum){
            subArrayData->leftIndex = 0;
            subArrayData->rightIndex = i;
            subArrayData->maxSum = leftMaxSum;
        }

        rightMaxSum = 0;
        for (j = i + 1; j >=0; --j){
            rightMaxSum += array[j];
            if (rightMaxSum > subArrayData->maxSum){
                subArrayData->leftIndex = j;
                subArrayData->rightIndex = i + 1;
                subArrayData->maxSum = rightMaxSum;
            }
        }
    }

}

这个是按照题目给的过程写的，虽然算法是正确的，但是时间复杂度为 n^2 不符合要求，正确的做法是用空间换取时间。

时间复杂度 n

typedef struct {
    int leftIndex;
    int rightIndex;
    int maxSum;
} SubArrayData;

void question4_1_5(int array[], int length, SubArrayData *subArrayData){
    int i = 0;
    SubArrayData maxSubArrays[length];
    
    maxSubArrays[0].leftIndex = 0;
    maxSubArrays[0].rightIndex = 0;
    maxSubArrays[0].maxSum = array[0];
    
    for (i = 1; i < length; ++i){
        if (maxSubArrays[i - 1].maxSum < 0){
            maxSubArrays[i].leftIndex = i;
            maxSubArrays[i].rightIndex = i;
            maxSubArrays[i].maxSum = array[i];
        }else {
            maxSubArrays[i].leftIndex = maxSubArrays[i - 1].leftIndex;
            maxSubArrays[i].rightIndex = i;
            maxSubArrays[i].maxSum = maxSubArrays[i - 1].maxSum + array[i];
        }
    }
    
    (*subArrayData) = maxSubArrays[0];
    
    for (i = 0; i < length; ++i){
        if (subArrayData->maxSum < maxSubArrays[i].maxSum){
            (*subArrayData) = maxSubArrays[i];
        }
    }
}

这个是正确的解法，算法维护了一个数组，这个数组储存这从起点到索引为 i 的数组的最大子数组，最后从这些最大子数组中找到那个最大的即为整个数组的最大子数组。