最大字?jǐn)?shù)組問題

暴力解法

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;
            }
        }
    }
}

算法基本過程：
遍歷數(shù)組元素，以每一個(gè)數(shù)組元素為最大子數(shù)組第一個(gè)元素尋找子數(shù)組。

時(shí)間復(fù)雜度為 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];
    }

}

算法基本過程：
將待處理數(shù)組在中點(diǎn)分隔成兩個(gè)子數(shù)組，最大子數(shù)組只可能在三個(gè)位置出現(xiàn)：

1 左邊的子數(shù)組

2 右邊的子數(shù)組

3 跨越中點(diǎn)的子數(shù)組

遞歸的查找這三個(gè)最大子數(shù)組，返回三者中最大的。

時(shí)間復(fù)雜度 nlg(n)

習(xí)題 4.1-5

時(shí)間復(fù)雜度 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;
            }
        }
    }

}

這個(gè)是按照題目給的過程寫的，雖然算法是正確的，但是時(shí)間復(fù)雜度為 n^2 不符合要求，正確的做法是用空間換取時(shí)間。

時(shí)間復(fù)雜度 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];
        }
    }
}

這個(gè)是正確的解法，算法維護(hù)了一個(gè)數(shù)組，這個(gè)數(shù)組儲存這從起點(diǎn)到索引為 i 的數(shù)組的最大子數(shù)組，最后從這些最大子數(shù)組中找到那個(gè)最大的即為整個(gè)數(shù)組的最大子數(shù)組。