結對開發實戰 (二)：二維陣列最大子陣列和問題

結對開發實戰 (二)：二維陣列最大子陣列和問題

延續一維版本，本次挑戰二維陣列最大子陣列和。採用「降維打擊」策略：將二維問題分解為多個一維問題，複用一維最大子陣列和邏輯，最終合併結果。記錄完整設計思路、C++ 實作碼、測試結果與心得。

問題定義

• 輸入：固定 3×3 整數矩陣 (由檔案 array.txt 讀取)
• 目標：找出所有連續子矩陣 (矩形區域) 元素和的最大值

降維策略

1. 第 1 行獨立 → 一維最大子陣列和
2. 第 2 行獨立 → 一維最大子陣列和
3. 第 1+2 行逐列相加 → 新一維陣列 → 一維最大子陣列和
4. 三者取最大

局限：此法僅處理「從第 1 行開始」的子矩陣，未涵蓋所有可能矩形區域 (如僅第 2 行、或第 2+3 行)。完整解法需雙重迴圈枚舉上下邊界，再降維。

核心程式碼 (節錄)

// 一維最大子陣列和 (複用上次邏輯)
int *shuchu(int m[], int sz, int xhy) {
    int c[10000], v[10000], *temp = malloc(2*sz*sizeof(int));
    for (int t = sz-xhy-1; t < sz; t++) c[t-sz+xhy+1] = m[t];
    for (int t = xhy; t >= 0; t--) {
        int sum = 0;
        for (int p = 0; p <= t; p++) sum += c[p];
        v[t] = sum; temp[t] = sum;
    }
    return temp; // 返回各長度前綴和陣列
}

// 主程式
int main() {
    int array[50][50], len1, len2;
    read(array, len1, len2); // 讀檔
    int x[3], y[3];
    for(int i=0;i<3;i++) { x[i]=array[0][i]; y[i]=array[1][i]; }

    int w[6], u[6], h[6], q=0, e=3;
    // 第1行所有子陣列和
    for(int i=2;i>=0;i--) {
        int *k = shuchu(x,3,i);
        for(int r=0;r=0;i--) {
        int *l = shuchu(y,3,i);
        for(int r=0;r
測試結果
程式成功編譯執行，輸出各行子陣列和、合併後和及最終最大值。截圖顯示矩陣讀取正確、中間過程輸出清晰。
心得與改進

    
邏輯分解能力關鍵：將二維問題映射到已解決的一維問題
    
函式複用節省開發時間，但需注意介面匹配 (此處 shuchu 返回指標需手動管理記憶體)
    
完整解法應參考「最大子矩陣和」經典演算法：固定上下行邊界 O(rows²)，列向降維 O(cols)，總體 O(rows²·cols)
    
結對中「導航員」負責邏輯驗證、「駕駛員」專注編碼，角色輪換顯著降低錯誤率

標準演算法補充
// 最大子矩陣和 O(n^3) 標準解法
int maxSubMatrix(int mat[][N], int rows, int cols) {
    int maxSum = INT_MIN;
    for (int top = 0; top < rows; top++) {
        int temp[cols] = {0};
        for (int bottom = top; bottom < rows; bottom++) {
            for (int c = 0; c < cols; c++) temp[c] += mat[bottom][c];
            // Kadane 算法求 temp 最大子陣列和
            int cur = 0, best = INT_MIN;
            for (int c = 0; c < cols; c++) {
                cur = max(temp[c], cur + temp[c]);
                best = max(best, cur);
            }
            maxSum = max(maxSum, best);
        }
    }
    return maxSum;
}
此次實戰強化了問題分解、代碼複用、演算法優化與結對協作技能。