Как найти индексы максимальной суммы элементов в непрерывном участке массива на C++?

Question

Вам даётся массив целых чисел. Необходимо найти такие два индекса i и j в этом массиве, что сумма a[i], a[i+1], a[i+2], … a[j] будет максимально возможной и вывести их.

Пример:

a = {-2,1,-3,4,-1,2,1,-5,4}

Тогда наибольшая сумма последовательных элементов находится между индексами 3 и 6: {4,-1,2,1}, сумма = 6. Необходимо вывести 3 и 6

Answer 1

#include <iostream>

using namespace std;

int main() {
    setlocale(0, "");

    int a[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int i = 0, j = 0, iMax = 0, jMax = 0, sumMax = 0, sumTemp = 0;

    for (; i < size(a); i++) {

        sumTemp = a[i];

        for (int j = i + 1; j < size(a); ++j) {
            sumTemp += a[j];
            if (sumTemp > sumMax) {
                iMax = i;
                jMax = j;
                sumMax = sumTemp;
            }
        }
    }

    cout << "Значение индексов " << iMax << " и " << jMax << " Сумма " << sumMax;
    return 0;
}

решение тривиальное, и далеко не оптимальное. Простой перебор с проверками

Answer 2

Линейное решение:

Если неотрицательных чисел в массиве нет, выбираем максимальный элемент и оба индекса ставим на него.
Проходим по элементам массива и считаем баланс.
Если текущий элемент неотрицательный и баланс 0, то запоминаем индекс начала последовательности.
Если текущий элемент отрицательный, сравниваем текущий баланс с лучшим и при необходимости заменяем установив концом отрезка прошлый элемент.
Текущий элемент добавляем к балансу.
Если баланс получился отрицательным, заменяем на 0.

Answer 3

#include <iostream>

int main() {
    int a[] = { -2,1,-3,4,-1,2,1,-5,4 };
    const int n = std::size(a);
    int answer = a[0],
        firstPos = 0,
        secondPos = 0,
        sum = 0,
        minimum = 0,
        min_pos = -1;
    for (int r = 0; r < n; ++r) {
        sum += a[r];

        int cur = sum - minimum;
        if (cur > answer) {
            answer = cur;
            firstPos = min_pos + 1;
            secondPos = r;
        }

        if (sum < minimum) {
            minimum = sum;
            min_pos = r;
        }
    }
    std::cout << "Summ: " << answer <<
        std::endl << "First Index: " << firstPos <<
        std::endl << "Second Index: " << secondPos;
}

БЛОГ НА HUSL

Как найти индексы максимальной суммы элементов в непрерывном участке массива на C++?

Ответы (3 шт):