В этой записи блога мы углубимся в решение проблемы максимального подмассива с помощью Java. Задача о максимальном подмассиве — это классическая алгоритмическая задача, в которой нам нужно найти непрерывный подмассив внутри массива, имеющий наибольшую сумму. Мы рассмотрим несколько способов решения этой проблемы, попутно предоставляя примеры кода и пояснения.

Метод 1: подход грубой силы
Подход грубой силы включает в себя проверку каждого возможного подмассива и вычисление его суммы. Мы отслеживаем максимальную сумму, обнаруженную на данный момент, и обновляем ее всякий раз, когда обнаруживается более высокая сумма. Вот код:

public int maxSubArray(int[] nums) {
    int maxSum = Integer.MIN_VALUE;
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        int currentSum = 0;
        for (int j = i; j < n; j++) {
            currentSum += nums[j];
            maxSum = Math.max(maxSum, currentSum);
        }
    }
    return maxSum;
}

Метод 2: алгоритм Кадане
Алгоритм Кадане — это эффективный подход, который использует динамическое программирование для решения проблемы максимального подмассива. Он поддерживает две переменные: currentSumи maxSum. currentSumотслеживает сумму текущего подмассива, а maxSumхранит максимальную сумму, обнаруженную на данный момент. Вот код:

public int maxSubArray(int[] nums) {
    int currentSum = nums[0];
    int maxSum = 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;
}

Метод 3: разделяй и властвуй
Подход «разделяй и властвуй» предполагает разбиение массива на более мелкие подмассивы и рекурсивное решение проблемы. Максимальный подмассив может находиться либо в левой половине, либо в правой половине, либо пересекать среднюю точку. Вот код:

public int maxSubArray(int[] nums) {
    return divideAndConquer(nums, 0, nums.length - 1);
}
private int divideAndConquer(int[] nums, int left, int right) {
    if (left == right) {
        return nums[left];
    }
    int mid = (left + right) / 2;
    int leftSum = divideAndConquer(nums, left, mid);
    int rightSum = divideAndConquer(nums, mid + 1, right);
    int crossingSum = crossingSum(nums, left, mid, right);
    return Math.max(Math.max(leftSum, rightSum), crossingSum);
}
private int crossingSum(int[] nums, int left, int mid, int right) {
    int leftSum = Integer.MIN_VALUE;
    int sum = 0;
    for (int i = mid; i >= left; i--) {
        sum += nums[i];
        leftSum = Math.max(leftSum, sum);
    }
    int rightSum = Integer.MIN_VALUE;
    sum = 0;
    for (int i = mid + 1; i <= right; i++) {
        sum += nums[i];
        rightSum = Math.max(rightSum, sum);
    }
    return leftSum + rightSum;
}

В этой статье мы рассмотрели различные методы решения проблемы максимального подмассива с помощью Java. Мы обсудили подход грубой силы, алгоритм Кадане и технику «разделяй и властвуй». Каждый метод имеет свои преимущества и сложности, поэтому важно выбрать наиболее подходящий подход с учетом ограничений задачи.