Найбільша сума суміжного підмасиву


Рівень складності Легко
Часто запитують у 24 * 7 Інноваційні лабораторії Аколіт Амазонка Д. Е. Шоу Факти Flipkart Похід Housing.com MakeMyTrip MetLife Microsoft Morgan Stanley Ола Кабіни оракул Номери OYO PayU Samsung Snapdeal Терадата Віза VMware Лабораторії Walmart Zoho
масив Динамічне програмування

Постановка проблеми

Вам дано масив цілих чисел. Постановка задачі вимагає з’ясувати найбільшу суміжну суміжну масиву. Це означає не що інше, як знайти підмасив (безперервні елементи), який має найбільшу суму серед усіх інших підмасивів у даному масиві.

Приклад

arr[] = {1, -3, 4, -2, 5, -6, 2}
[2, 4]

Пояснення: Підмасив, що починається від індексу 2 до індексу 4, має найбільшу суму 7 усередині масиву. Будь-який інший підмасив дасть суму менше 7.

Найбільша сума суміжного підмасиву

 

arr[] = {1, -3, 4, -1, 4, -2, 5, -6, 2}
[2, 6]

Пояснення: Підмасив, що починається з індексу 2 до індексу 6, має найбільшу суму 10 у масиві.

 

Алгоритм суміжної задачі найбільшої суми

1. Set the maxValue to the minimum value an integer can hold (INT_MIN / Integer.MIN_VALUE) and maxPoint to 0.
2. Set start, end, s to 0.
3. Traverse the array starting from i=0 to i<size(length of the array).
  1. Add the maxPoint and arr[i] and update it into the maxPoint.
  2. Check if maxValue is less than maxPoint, then update the following:
    1. maxValue = maxPoint
    2. start=s
    3. end=i
  3. Check if the maxPoint is less than 0, then update
    1. maxPoint=0
    2. s=i+1
4. Print ‘start’ and ‘end’ as an index and the maxValue as the largest sum.

Пояснення

Ми дали масив цілих чисел. Ми попросили з’ясувати найбільшу суміжну суміжну масиву. Він також може містити цілі від’ємні та додатні числа. Ми повинні розглядати всі ці справи. Для цього ми збираємось перейти масив раз на раз, а отже, він має час складності О (п). Ми знайдемо максимальну суміжну суму підмасиву за лінійною часовою складністю.

Встановіть деякі значення, наприклад maxValue до мінімального значення, яке може містити ціле число, maxPoint до 0, і старт, кінець, і s до 0. Почніть обводити масив на довжину n. Додайте поточний елемент масиву до суми maxPoint. Зберігайте його в maxPoint, кожен раз значення i зростаючи в циклі, ми робимо цю операцію. Ми вже визначили значення maxValue до мінімального значення цілого числа та перевірте, чи maxValue менше, ніж maxPoint. Якщо це правда, тоді ми збираємось оновити значення maxValue з maxPoint, почніть до s. Ця змінна старту встановить значення початкового діапазону суміжного підмасиву, і ми маємо кінець, який ми оновлюємо за допомогою i (змінна циклу).

Ми зараз перевіримо, чи maxPoint менше 0, означає додавання значень масиву дотепер від’ємне. Потім ми знову оновлюємо значення maxPoint до 0 і s до i + 1. Це s допоможе нам знову у встановленні значення початкового діапазону та допоможе нам з’ясувати найбільший підмасив суми. Цей maxPoint ми будемо ініціалізувати до нуля, оскільки нам потрібно знайти найбільшу суму, а потім ми надрукуємо значення start і end як початковий і кінцевий показник необхідного підмасиву найбільшої суми. Якщо ми використовуємо цей підхід, то за один прохід ми можемо знайти найбільшу суміжну суміжну масиву.

 

Код для суміжної задачі найбільшої суми

Код С ++

#include<bits/stdc++.h>
using namespace std;

// This Function prints the Largest Sum Contiguous Subarray
void getLargestSumContiguousSubarray(int arr[], int size)
{
    // initialising variables with starting values
    int maxValue = INT_MIN;
    int  maxPoint = 0;
    int start =0, end = 0, s=0;

    for (int i=0; i< size; i++ )
    {
        maxPoint += arr[i];

        if (maxValue < maxPoint)
        {
            maxValue = maxPoint;
            start = s;
            end = i;
        }

        if (maxPoint < 0)
        {
            maxPoint = 0;
            s = i + 1;
        }
    }
    cout << "Sub-Array starting from "<< start<< " to "<< end<< " has a largest sum of " <<maxValue;
}
int main()
{
    int arr[] = {1, -3, 4, -2, 5, -6, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    getLargestSumContiguousSubarray(arr, n);
    return 0;
}
Sub-Array starting from 2 to 4 has a largest sum of 7

 

Код Java

class LargestSumSubArray
{
    // This Function prints Largest Sum Contiguous Subarray
    public static void getLargestSumContiguousSubarray(int arr[], int size)
    {
        // initialising variables with starting values
        int maxValue = Integer.MIN_VALUE;
        int  maxPoint = 0;
        int start =0, end = 0, s=0;

        for (int i=0; i< size; i++ )
        {
            maxPoint += arr[i];

            if (maxValue < maxPoint)
            {
                maxValue = maxPoint;
                start = s;
                end = i;
            }

            if (maxPoint < 0)
            {
                maxPoint = 0;
                s = i + 1;
            }
        }
        System.out.println("Sub-Array starting from "+ start + " to "+ end + " has a largest sum of " + maxValue);
    }
    public static void main(String [] args)
    {
        int arr[] = {1, -3, 4, -2, 5, -6, 2};
        int n = arr.length;
        getLargestSumContiguousSubarray(arr, n);
    }
}
Sub-Array starting from 2 to 4 has a largest sum of 7

Аналіз складності

Складність часу

Оскільки ми запускаємо єдиний цикл над вхідним масивом розміром n. Таким чином, алгоритм найбільшої суміжної суміжної масиву має лінійну часову складність. О (п) де "N" - кількість елементів у масиві.

Складність простору

Для збереження цілих чисел ми використали єдиний 1D масив вводу. Таким чином вносячи складність лінійного простору до найбільшої суміжної задачі про підмасив. О (п) де "N" - кількість елементів у масиві.