Самая вялікая сумежная сумежная падмасіў  


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

Пастаноўка праблемы  

Вам дадзены масіў цэлых лікаў. Пастаноўка праблемы патрабуе высветліць самую вялікую сумежную падмасіў. Гэта азначае не што іншае, як знайсці падмасіў (бесперапынныя элементы), які мае найбольшую суму сярод усіх іншых падмасіваў у дадзеным масіве.

Прыклад  

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

Тлумачэнне: Падмасіў, пачынаючы ад індэкса 2 да індэкса 4, мае найбольшую суму 7 у масіве. Любы іншы падмасіў дасць суму, меншую за 7.

Самая вялікая сумежная сумежная падмасіўPin

 

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, пачніце з. Гэта стартавая зменная ўсталюе значэнне стартавага дыяпазону сумежнага падмасіва, і ў нас ёсць канец, які мы абнаўляем з дапамогай i (зменнай цыкла).

Зараз мы праверым, ці будзе maxPoint менш за 0, азначае даданне значэнняў масіва да гэтага часу адмоўнае. Затым мы зноў абнаўляем значэнне maxPoint да 0 і s да i + 1. Гэта s дапаможа нам зноў наладзіць значэнне стартавага дыяпазону і дапаможа даведацца найбольшую падмасіў сумы. Гэты maxPoint мы будзем ініцыялізаваць нулём, таму што мы павінны высветліць самую вялікую суму, а потым мы збіраемся надрукаваць значэнне пачатку і канца ў якасці пачатковай і канчатковай прыкмет неабходнага падмасіва самай вялікай сумы. Калі мы выкарыстоўваем гэты падыход, мы можам знайсці самую вялікую сумежную падмасіў за адзін праход.

 

Код для сумежнай задачы найбольшай сумы  

Код C ++

#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. Такім чынам, алгарытм найбольшай сумежнай падмасіва мае лінейную часавую складанасць. Аб (п) дзе "П" - колькасць элементаў у масіве.

Касмічная складанасць

Для захоўвання цэлых лікаў мы выкарысталі адзін 1D-масіў. Такім чынам, укладваючы лінейную прасторавую складанасць у задачу найбуйнейшай сумы, якая знаходзіцца побач. Аб (п) дзе "П" - колькасць элементаў у масіве.