算法導論4.1-2 最大子數組問題的暴力解

題目

對最大子數組問題，編寫暴力求解方法的僞代碼，其運作時間應該是

θ(n^2)

。

題解

θ(n^2)

的方法是通過儲存二維數組的上一個計算結果，即

i..j

的和，來計算

i..j+1

的和。

用

c++

代碼寫一遍。

#include <cstdio>
#include <cstring>
#include <climits>

struct Sub {
    int low;
    int high;
    int sum;
};

Sub FindMaximumSubarray(const int array[], int count) {
    int sum[count][count];
    Sub maxSub = { 0, 0, -INT_MIN};
    for (int i = 0; i < count; ++i) {
        for (int j = i; j < count; ++j) {
            if (i != j) {
                sum[i][j] = sum[i][j-1] + array[j];
            } else {
                sum[i][j] = array[j];
            }
            if (sum[i][j] > maxSub.sum) {
                maxSub = { i, j, sum[i][j] };
            }
        }
    }
    return  maxSub;
}

int main() {
    int arr[] = { 13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7 };
    Sub ans = FindMaximumSubarray(arr, sizeof(arr)/sizeof(arr[0]));
    printf("low = %d, high = %d, sum = %d", ans.low, ans.high, ans.sum);
    return 0;
}
           

附上github代碼位址: https://github.com/FengHaiTongLuo/Introduction-to-Algorithms-Prac/blob/main/prac_4.1-2.cpp

通過微信公衆号”風海銅鑼技術君“的菜單可以加我入面試交流的”程式員卷卷群“。