Ищем наибольшую сумму внутри массива

Question

У меня есть заданный массив [-2 -3 4 -1 -2 1 5 -3], поэтому самая большая сумма будет 7 (числа от 3-го до 7-го индекса).Этот массив является простым примером, в программе должны быть элементы пользовательского ввода и длина массива.

Мой вопрос: как определить, какая сумма будет наибольшей?
Я создал сумму из всех чисел и сумму только положительных чисел, но положительная сумма была бы большой, но я не использовал-1 и -2 после этого 3-го индекса из-за «оператора IF», поэтому моя сумма равна 10, а решение не подходит.

Answer 1

Я предполагаю, что ваши вопросы - найти непрерывный подмассив (содержащий хотя бы одно число), который имеет наибольшую сумму.Иначе, проблема довольно тривиальна, так как вы можете просто выбрать все положительные числа.

Есть 3 решения, которые лучше, чем решение с грубой силой O (N ^ 2).N - длина входного массива.

1. Динамическое программирование.O (N) время выполнения, O (N) пробел

Поскольку подмассив содержит хотя бы одно число, мы знаем, что существует только N возможных кандидатов: подмассив, заканчивающийся на A [0], A [1] ...... A [N - 1] Для подмассива, заканчивающегося в A [i], мы имеем следующую оптимальную подструктуру: maxSum [i] = max of {maxSum [i - 1] + A [i], A [i]};

class Solution {
    public int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE;
        if(nums == null || nums.length == 0) {
            return max;
        }
        int[] maxSum = new int[nums.length + 1];
        for(int i = 1; i < maxSum.length; i++) {
            maxSum[i] = Math.max(maxSum[i - 1] + nums[i - 1], nums[i - 1]);
        }
        for(int i = 1; i < maxSum.length; i++) {
            max = Math.max(maxSum[i], max);
        }
        return max;
    }
}

Префиксная сумма, O (N) время выполнения, O (1) пробел

Поддерживайте переменную минимальной суммы при выполнении итерации по всему массиву.При посещении каждого числа во входном массиве обновите переменную суммы префикса currSum.Затем обновите максимальную и минимальную суммы, указанные в следующем коде.

class Solution {
    public int maxSubArray(int[] nums) {
        if(nums == null || nums.length == 0) {
            return 0;
        }
        int maxSum = Integer.MIN_VALUE, currSum = 0, minSum = 0;
        for(int i = 0; i < nums.length; i++) {
            currSum += nums[i];
            maxSum = Math.max(maxSum, currSum - minSum);
            minSum = Math.min(minSum, currSum);
        }
        return maxSum;
    }
}

Разделяй и властвуй, O (N * logN) время выполнения

Разделите исходную задачу на две подзадачи и рекурсивно примените этот принцип, используя следующую формулу.

Пусть A [0, .... midIdx] будет левой половиной A, A [midIdx + 1, ..... A.length - 1] будет правой половиной A. leftSumMax - ответ левой подзадачи, rightSumMax - этоОтвет правильной подзадачи.

Окончательный ответ будет одним из следующих 3: 1. используются только числа из левой половины (решается левой подзадачей) 2. используются только числа из правой половины (решается правой подзадачей) 3. использует числа из левой и правой половин (решается за O (n) раз)

class Solution {
    public int maxSubArray(int[] nums) { 
        if(nums == null || nums.length == 0)
        {
            return 0;
        }
        return maxSubArrayHelper(nums, 0, nums.length - 1);
    }
    private int maxSubArrayHelper(int[] nums, int startIdx, int endIdx){
        if(startIdx == endIdx){
            return nums[startIdx];
        }
        int midIdx = startIdx + (endIdx - startIdx) / 2;
        int leftMax = maxSubArrayHelper(nums, startIdx, midIdx);
        int rightMax = maxSubArrayHelper(nums, midIdx + 1, endIdx);
        int leftIdx = midIdx, rightIdx = midIdx + 1;
        int leftSumMax = nums[leftIdx], rightSumMax = nums[rightIdx];
        int leftSum = nums[leftIdx], rightSum = nums[rightIdx];
        for(int i = leftIdx - 1; i >= startIdx; i--){
            leftSum += nums[i];
            leftSumMax = Math.max(leftSumMax, leftSum);
        }
        for(int j = rightIdx + 1; j <= endIdx; j++){
            rightSum += nums[j];
            rightSumMax = Math.max(rightSumMax, rightSum);
        }
        return Math.max(Math.max(leftMax, rightMax), leftSumMax + rightSumMax);
    }
}

Answer 2

Попробуйте это:

1. найдите первое положительное число, смещение i.
2. добавить следующие положительные числа, получая сумму sum, последнее смещение j. Если эта сумма больше вашей текущей лучшей суммы, она становится текущей лучшей суммой со смещениями от i до j.
3. добавляйте следующие отрицательные числа, пока не получите другое положительное число. Если эта отрицательная сумма больше по абсолютной величине, чем sum, начните новую сумму с этого смещения, в противном случае продолжите с текущей суммы.
4. вернитесь к шагу 2.

Остановите это, когда доберетесь до конца массива. Найдена лучшая положительная сумма.

Если положительная сумма не может быть найдена, найдите наименее отрицательное значение, эта единственная запись будет вашей лучшей нетривиальной суммой.