Рубрики

Программа C / C ++ для непрерывного массива с наибольшей суммой

Напишите эффективную программу для поиска суммы смежных подмассивов в одномерном массиве чисел с наибольшей суммой.

// C ++ программа для вывода наибольшей суммы непрерывных массивов
#include <climits>
#include <iostream>

using namespace std;

  

int maxSubArraySum(int a[], int size)

{

    int max_so_far = INT_MIN, max_ending_here = 0;

  

    for (int i = 0; i < size; i++) {

        max_ending_here = max_ending_here + a[i];

        if (max_so_far < max_ending_here)

            max_so_far = max_ending_here;

  

        if (max_ending_here < 0)

            max_ending_here = 0;

    }

    return max_so_far;

}

  
/ * Драйвер программы для проверки maxSubArraySum * /

int main()

{

    int a[] = { -2, -3, 4, -1, -2, 1, 5, -3 };

    int n = sizeof(a) / sizeof(a[0]);

    int max_sum = maxSubArraySum(a, n);

    cout << "Maximum contiguous sum is " << max_sum;

    return 0;

}

Выход:

Maximum contiguous sum is 7

Выше программа может быть оптимизирована дальше, если мы сравним max_so_far с max_ending_here, только если max_ending_here больше 0.

C ++

int maxSubArraySum(int a[], int size)

{

    int max_so_far = 0, max_ending_here = 0;

    for (int i = 0; i < size; i++) {

        max_ending_here = max_ending_here + a[i];

        if (max_ending_here < 0)

            max_ending_here = 0;

  

        / * Не сравнивать по всем элементам. Сравнить только

          когда max_ending_here> 0 * /

        else if (max_so_far < max_ending_here)

            max_so_far = max_ending_here;

    }

    return max_so_far;

}

Пожалуйста, обратитесь к полной статье о самой большой сумме смежных подмассива для более подробной информации!

Рекомендуемые посты:

Программа C / C ++ для непрерывного массива с наибольшей суммой

0.00 (0%) 0 votes