結對編程實戰（五）：首尾相連二維數組最大子數組和

結對編程實戰（五）：首尾相連二維數組最大子數組和

合作夥伴：高揚、韓雪東

一、題目與設計思路

需求：在一維首尾相連最大子數組和解決方案基礎上，擴展至二維數組。數組首尾相接形成環狀結構，求和最大的子數組。

設計思想：將一維環狀最大子數組算法與二維最大子矩陣算法融合。利用列向累加將二維問題轉化為一維序列，再套用環狀最大子數組邏輯，在課堂限時內快速實現。

二、核心算法解析

代碼採用 C++ 風格 C 語言（iostream.h、fstream.h），關鍵函數：

• shuchu()：計算一維數組在指定循環條件下的所有前綴和，返回最大值數組
• maxs()：求數組最大值
• 主流程：讀取矩陣 → 對每行獨立計算環狀最大子數組和 → 兩行疊加求組合最大值 → 矩陣循環移位重複上述過程 → 取全局最大值

三、源代碼（關鍵片段）

// 環狀一維最大子數組和輔助函數
int *shuchu(int m[], int szcdx, int xhy) {
    int c[10000], v[10000];
    int o = 2 * szcdx;
    int *temp = new int[o];
    // 將數組尾部 xhy+1 個元素複製到 c 頭部，模擬環狀
    for (int t = szcdx - xhy - 1; t < szcdx; t++)
        c[t - szcdx + 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;
    }
    // 提取最大值序列
    int max = v[0];
    for (int t = 0; t < xhy + 1; t++) {
        if (max <= v[t]) max = v[t];
        temp[t] = v[t];
    }
    return temp;
}

// 主函數邏輯縮寫
int main() {
    int array[MAXSIZE][MAXSIZE], len1, len2;
    read(array, len1, len2); // 從文件讀取
    // 對第 0、1 行分別計算環狀最大子數組和序列 w, u
    // 疊加得 h = w + u，取三者最大值
    // 矩陣左移一位（首尾相連模擬），重複計算，更新全局最大值
}

四、運行結果

五、心得與反思

「當你把系統的一塊新部件放進去，總要看看之後的 5 年或 10 年自己會不會後悔——你是否能擴展它、替換它。」——《夢斷代碼》

• 基礎決定上層建築：扎實的一維算法積累讓二維擴展水到渠成。
• 代碼可擴展性：模塊化設計（shuchu/maxs 分離）大幅降低修改成本。
• 1+1 > 2：結對編程在效率與思路廣度上顯著優於單打獨鬥，團隊協作同理。

六、現場照片