编辑代码

public class MaxSubarraySum {
    // 方法1：暴力枚举法 O(n²)
    public static int bruteForce(int[] nums) {
        int maxSum = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int currentSum = 0;
            for (int j = i; j < nums.length; j++) {
                currentSum += nums[j];
                if (currentSum > maxSum) {
                    maxSum = currentSum;
                }
            }
        }
        return maxSum;
    }

    // 方法2：分治法 O(n log n)
    public static int divideAndConquer(int[] nums) {
        return conquer(nums, 0, nums.length - 1);
    }

    private static int conquer(int[] nums, int left, int right) {
        if (left == right) return nums[left];
        int mid = (left + right) / 2;
        int leftMax = conquer(nums, left, mid);
        int rightMax = conquer(nums, mid + 1, right);
        int crossMax = crossSum(nums, left, mid, right);
        return Math.max(Math.max(leftMax, rightMax), crossMax);
    }

    private static int crossSum(int[] nums, int left, int mid, int right) {
        int leftSum = Integer.MIN_VALUE;
        int current = 0;
        for (int i = mid; i >= left; i--) {
            current += nums[i];
            if (current > leftSum) leftSum = current;
        }
        int rightSum = Integer.MIN_VALUE;
        current = 0;
        for (int i = mid + 1; i <= right; i++) {
            current += nums[i];
            if (current > rightSum) rightSum = current;
        }
        return leftSum + rightSum;
    }

    // 方法3：动态规划法 O(n)
    public static int dynamicProgramming(int[] nums) {
        if (nums.length == 0) return 0;
        int maxSum = nums[0];
        int currentSum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            currentSum = Math.max(nums[i], currentSum + nums[i]);
            maxSum = Math.max(maxSum, currentSum);
        }
        return maxSum;
    }

    // 测试用例
    public static void main(String[] args) {
        int[] testCase = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        
        System.out.println("测试用例数组: [-2, 1, -3, 4, -1, 2, 1, -5, 4]");
        System.out.println("暴力法结果: " + bruteForce(testCase));
        System.out.println("分治法结果: " + divideAndConquer(testCase));
        System.out.println("动态规划法结果: " + dynamicProgramming(testCase));
        
        // 边界测试（全负数）
        int[] allNegative = {-1, -2, -3};
        System.out.println("\n边界测试（全负数）: [-1, -2, -3]");
        System.out.println("暴力法结果: " + bruteForce(allNegative));
        System.out.println("分治法结果: " + divideAndConquer(allNegative));
        System.out.println("动态规划法结果: " + dynamicProgramming(allNegative));
    }
}