Големина на под-низата со максимална сума


Ниво на тешкотија Лесно
Често прашувано во Coursera GreyOrange UHG Optum Xome
Низа Динамичко програмирање

Изјава за проблем

Ти е даден низа на цели броеви. Дадената низа може да содржи и позитивни и негативни броеви. Откријте ја големината на под-низата со максимална сума.

пример

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

Објаснување: 2 -1 + 4 + 3 = 8 е максимална сума на должината 4


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

Објаснување: 1 + 2 = 3 е максимален збир на должина 2

Алгоритам

1. Set the maxVal to the minimum value of an integer and maxPoint to 0, start, end, and s to 0.
2. Starting from i=0 to i<size(length of the array).
  1. Sum up the value of maximumPoint and arr[i] and store into the maximumPoint.
  2. Check if maxVal is less than maxPoint, then update the following:
    maxVal = maxPoint
    start=s
    nd=i
  3. Check if the maximumPoint is less than 0, then update
    maximumPoint=0
    s=i+1
3. Return the value (end – start + 1).

Објаснување за пресметување на големината на под-низата со максимален збир

Со оглед на низа цели броеви. Нашата задача е да ја пронајдеме должината на под-низа која има максимална сума. Може да содржи и негативни и позитивни цели броеви. Одиме напречни изложбата само еднаш и последователно, има временска сложеност на O (n). Лоцирајте го најголем вкупна под-вредност во линеарна временска комплексност.

Поставете одредени вредности на променливата, како на пр maxValue до минималната вредност на ан Цел број, maxPoint до 0, и Почеток, крајот, и s до 0. Започнете да ја поминувате низата до должината n. Вклучете го тековниот елемент на низата во вкупниот maxPoint и зачувајте го во maxPoint, секој пат кога вредноста на i ќе се зголеми во јамката.

Поставете ја вредноста на maxValue до минималната вредност на цел број и проверете ја можноста дека maxValue не е поголема од maxPoint, во случај да е валидна, во тој момент ќе ја ажурираме вредноста на maxValue од maxPoint, започнете со s, оваа почетна променлива ќе ја постави вредноста на почетниот опсег на соседната под-низа и имаме крај, што ќе го ажурираме со i.

Willе провериме дали maxPoint е помал од 0, ова значи дека збирот на под-низата е негативен, во тој момент повторно ќе ја ажурираме вредноста на maxPoint на 0 и s на i + 1, ова ќе помогнете ни повторно во поставувањето на вредноста на почетниот опсег и помогнете ни при откривањето на најголемата подгрупа за суми. Оваа максимална точка ќе ја иницијализираме како нула бидејќи треба да ја најдеме најголемата сума и потоа ќе ја вратиме вредноста како крај-почеток + 1. Оваа повратна вредност ќе биде најголемата должина на под-низата од максималниот збир.

големина на под-низата со максимална сума

Имплементација во C ++ за наоѓање на големината на под-низата со максимална сума

#include<bits/stdc++.h>

using namespace std;

int getSizeMaxSum (int arr[], int size)
{
    int maxVal = INT_MIN, maximumPoint = 0,
        start =0, end = 0, s=0;

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

        if (maxVal < maximumPoint)
        {
            maxVal = maximumPoint;
            start = s;
            end = i;
        }

        if (maximumPoint < 0)
        {
            maximumPoint = 0;
            s = i + 1;
        }
    }

    return (end - start + 1);
}
int main()
{
    int arr[] = {1, -2, 1, 1, -2, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << getSizeMaxSum(arr, n);
    return 0;
}
2

 

Имплементација во Java за големината на под-низата со максимална сума

class SubArraySizeMaximumSum
{

    public static int getSizeMaxSum (int arr[], int size)
    {
        int maxVal = Integer.MIN_VALUE,
            maximumPoint = 0,start = 0,
            end = 0, s = 0;

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

            if (maxVal < maximumPoint)
            {
                maxVal = maximumPoint;
                start = s;
                end = i;
            }

            if (maximumPoint < 0)
            {
                maximumPoint = 0;
                s = i + 1;
            }
        }
        return (end - start + 1);
    }
    public static void main(String[] args)
    {
        int arr[] = {1, -2, 1, 1, -2, 1};
        int n = arr.length;
        System.out.println(getSizeMaxSum(arr, n));
    }
}
2

Анализа на сложеност

Временска комплексност

Тој) каде „Н“ е бројот на елементи во низата. Користевме само една јамка само за пресекување на низата еднаш, правејќи го тоа линеарно решение за сложеност на времето.

Комплексноста на просторот

Тој) каде „Н“ е бројот на елементи во низата. Бидејќи користевме единечна низа со големина n, имаме и линеарна просторна сложеност.