የሰባራሪው መጠን በከፍተኛው ድምር


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ Coursera ግሬይ ብርቱካናማ 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).

የከፍተኛው ድምር ንዑስ ክፍልን ለማስላት ማብራሪያ

የቁጥር ቁጥሮች ብዛት ይሰጣቸዋል። የእኛ ተግባር የ ከፍተኛ ድምር ያለው ንዑስ ቡድን. እሱ አሉታዊ እና አዎንታዊ የቁጥር ቁጥሮችም ሊኖረው ይችላል። እየሄድን ነው መተላለፊያ ኤግዚቢሽኑ ለአንዴ እና ለመጨረሻ ጊዜ ብቻ የኦ (n) የጊዜ ውስብስብነት አለው ፡፡ ቦታውን ያግኙ ትልቁ ንዑስ-እሴት ድምር በመስመራዊ ውስብስብነት።

እንደ ተለዋዋጭ የተወሰኑ እሴቶችን ያዘጋጁ ከፍተኛ ዋጋ ወደ አንድ አነስተኛ እሴት ኢንቲጀር, maxPoint እስከ 0 ፣ እና መጀመሪያ, መጨረሻ, እና s እስከ 0. ድረስ ድርድርን እስከ ርዝመቱ n ማቋረጥ ይጀምሩ ፡፡ የአሁኑን የድርጅት ንጥረ ነገር በጠቅላላው ከፍተኛው ነጥብ ውስጥ ይጨምሩ እና የ ‹i› በሉፉ ውስጥ በሚጨምርበት በእያንዳንዱ ጊዜ ወደ maxPoint ውስጥ ያከማቹ ፡፡

የ “MaxValue” ዋጋን ወደ ኢንቲጀር አነስተኛ እሴት ያቀናብሩ እና ከፍተኛው እሴት ከ maxPoint የማይበልጥ መሆኑን በመጥቀስ ያረጋግጡ ፣ ልክ ከሆነ ፣ በዚያ ጊዜ የ maxValue ዋጋን ከ maxPoint እናሻሽላለን ፣ ጀምር ወደ s ፣ ይህ የመጀመሪያ ተለዋዋጭ ተጓዳኝ ንዑስ ረድፍ የመነሻ ክልል ዋጋን ያበጃል እና እኛ አለን በ i እናዘምነዋለን መጨረሻ።

አሁን maxPoint ከ 0 በታች ከሆነ አሁን እንፈትሻለን ፣ ይህ ንዑስ-ድርድሩ ድምር አሉታዊ መሆኑን ያሳያል ፣ በዚያን ጊዜ የ maxPoint ዋጋን እንደገና ወደ 0 እና s ወደ i + 1 እናሻሽላለን ፣ ይህ 's' will የመነሻ ክልል ዋጋን በማቀናጀት እንደገና ይረዱናል እና ትልቁን ንዑስ ንዑስ ቡድን ለማወቅ ይረዳናል ፡፡ ይህ ከፍተኛ ነጥብ እኛ ትልቁን ድምር መፈለግ ስላለብን እንደ ዜሮ እንጀምራለን ከዚያ በኋላ ዋጋውን እንደ መጀመሪያ-ጅምር + 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

 

በከፍተኛው ድምር ለ ‹ንዑስ ክፍል› መጠን በጃቫ ውስጥ መተግበር

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) የት “N” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው። ድርድርን ለማቋረጥ አንድ ጊዜ ብቻ ተጠቅመናል ፣ ስለሆነም የመስመር ጊዜ ውስብስብነት መፍትሄ ያደርገዋል ፡፡

የቦታ ውስብስብነት

ሆይ (n) የት “N” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው። እኛ አንድ ነጠላ የመጠን ድርድርን ስለ ተጠቀመን ፣ እኛ እንዲሁ የመስመራዊ የቦታ ውስብስብነት አለን።