您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 綜合教學

Java 實作最大子數組和演算法：課堂練習完整解析

編輯：Java 綜合教學

Java 實作最大子數組和演算法：課堂練習完整解析

最大子數組和問題是經典的演算法題目，目標是找出整數陣列中連續子數組的最大和值。本文詳細記錄一次課堂練習的完整實作過程，包含設計思路、原始碼分析、執行結果與程式優化心得。

一、設計思路

本程式採用單一主函數完成所有邏輯，核心流程分為三個階段：

資料輸入：定義整數陣列，透過 Scanner 讓使用者輸入陣列長度與元素值。
正負零分類統計：遍歷陣列統計正數、負數與零的個數，作為後續分支判斷的依據。
分情況處理邏輯：根據統計結果分為四種情況執行對應策略：

全為負數：最大子數組和即為陣列中最大的負數（最接近零）。
僅含負數與零：最大和為 0（選擇空子數組或單一零元素）。
全為非負數：最大和為所有元素總和。
正負零混合：採用合併相鄰同號元素、篩選非零元素、動態規劃式合併正負區段等步驟計算最大和。

二、原始碼完整解析

以下為完整的 Java 原始碼，已整理格式並修正轉義字元：

/*
 * For the maximum of the subarray of an integer array
 * Start time: 2016/4/8 16:50
 * End time: 2016/4/8 18:30
 * Author: Jing
 */
package arraymax;

import java.util.*;

public class SumArray {

    public static void main(String[] args) {
        Scanner sca = new Scanner(System.in);
        System.out.println("請輸入整數陣列的元素個數：");
        int num = sca.nextInt();

        int a[] = new int[num];
        int b[] = new int[num]; // 暫存陣列
        int i;

        System.out.println("請輸入此組整數陣列：");
        for (i = 0; i < num; i++) {
            a[i] = sca.nextInt();
        }

        int l = 0, j = 0, k = 0, sum = 0, max;

        // 統計正負零分佈
        for (i = 0; i < num; i++) {
            if (a[i] >= 0) j++;
            if (a[i] < 0) k++;
            if (a[i] == 0) l++;
        }

        // 情況 1：全為負數
        if (k == num) {
            max = a[0];
            for (i = 1; i < num; i++) {
                if (max < a[i]) max = a[i];
            }
            System.out.println("最大子數組和為 " + max);
        }
        // 情況 2：只有負數和 0
        else if ((l + k) == num) {
            System.out.println("最大子數組和為 0");
        }
        // 情況 3：全為非負數
        else if (j == num) {
            for (i = 0; i < num; i++) sum += a[i];
            System.out.println("最大子數組和為 " + sum);
        }
        // 情況 4：正負零混合
        else {
            // 步驟 1：合併相鄰同號元素
            for (i = 0; i < num - 1; i++) {
                if (a[i] >= 0 && a[i+1] >= 0) {
                    a[i+1] = a[i] + a[i+1];
                    a[i] = 0;
                }
                if (a[i] < 0 && a[i+1] < 0) {
                    a[i+1] = a[i] + a[i+1];
                    a[i] = 0;
                }
            }

            // 步驟 2：將非零元素壓縮到 b 陣列
            k = 0; j = 0;
            while (k < num) {
                if (a[k] != 0) {
                    b[j] = a[k];
                    j++;
                }
                k++;
            }

            // 步驟 3：確定起始索引（跳過開頭負數）
            if (b[0] < 0) i = 1;
            else i = 0;

            // 步驟 4：動態合併「正-負-正」區段
            while (i < j - 2) {
                if (b[i] > (-b[i+1]) && (-b[i+1]) < b[i+2]) {
                    b[i+2] = b[i] + b[i+1] + b[i+2];
                    b[i] = 0;
                    b[i+1] = 0;
                    i += 2;
                } else {
                    i += 2;
                }
            }

            // 步驟 5：取最大值
            max = b[0];
            for (i = 1; i < j; i++) {
                if (max < b[i]) max = b[i];
            }
            System.out.println("最大子數組和為 " + max);
        }
    }
}