ረጅሙ እየጨመረ የሚሄድ ውጤት


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ የ Adobe አማዞን Citrix የኮድ ቁጥር ፌስቡክ google የ Microsoft ሳምሰንግ ቮሆ
የሁለትዮሽ ፍለጋ ተለዋዋጭ ፕሮግራም ሊስ።

እኛ አንድ ተሰጥቶናል ደርድር የማይነጣጠሉ የቁጥር ቁጥሮች እና በጣም ረዘም ያለ ቀጣይነት ማግኘት አለብን።

  • ተከታይነቱ ተከታታይ መሆን የለበትም
  • ተከታይነቱ እየጨመረ ይሄዳል

በጥቂቱ ምሳሌዎች በተሻለ እንረዳ ፡፡

ለምሳሌ

ግቤት

[9, 2, 5, 3, 7, 10, 8]

ዉጤት

4

ማስረጃ

ረጅሙ እየጨመረ ያለው ቀጣይነት [2,3,7,10] ነው።

አቀራረብ 1: የደስታ ኃይል

ይህ አካሄድ ሁሉንም ሊሆኑ የሚችሉ ንዑስ ክፍሎችን በመመልከት በተፈጥሮ ውስጥ እየጨመረ ያለውን ረጅሙን ተከታይ ማግኘትን ያካትታል ፡፡

አሁን በአንድ ድርድር ውስጥ የ ith ኢንቲጀርን በምንጎበኝ ቁጥር ሁለት ጉዳዮች ሊኖሩ ይችላሉ ፡፡

  • በቀጣዩ ውስጥ ሊካተት ይችላል ማለትም ከቀዳሚው ንጥረ ነገር ይበልጣል
  • ከቀዳሚው ንጥረ ነገር ያንሳል እና በተከታዩ ውስጥ ሊካተት አይችልም

ነገር ግን ንጥረ ነገሩን በተወሰነ ቦታ ላይ ብናካትት ወይም ባይኖርም እስከዚያ ነጥብ ድረስ የተወሰነ ርዝመት እየጨመረ የሚሄድ እና እስከዚያ ጊዜ ድረስ የተፈጠረውን ከፍተኛውን ርዝመት መመለስ እንችላለን ፡፡ ያንን በተሻለ በኮድ ቅንጥብ (በጃቫ እና ሲ ++)

የጃቫ ፕሮግራም ረዘም ላለ ጊዜ ለሚቀጥለው ውጤት

class Solution 
{
    public int helper(int[] nums,int prev,int cur)
    {
        if(cur==nums.length)
            return 0;
        int on_include=0;
        //If the element at current index is greater than 
        //previous element we add to the length of subsequence
        if(nums[cur]>prev)
            on_include=helper(nums,nums[cur],cur+1)+1;
        //Even if we are not there must be an increasing subsequence
        int on_ignore=0;
        on_ignore=helper(nums,prev,cur+1);
        return(Math.max(on_include,on_ignore));
    }
    public int lengthOfLIS(int[] nums) 
    {
        int max=helper(nums,Integer.MIN_VALUE,0);
        return max;
    }
}

C ++ ፕሮግራም ረዘም ላለ ጊዜ ለሚጨምር

class Solution 
{
public:
    int max(int a,int b)
    {
        if(a>b)
            return a;
        else
            return b;
    }
public:
    int helper(vector<int> nums,int prev,int cur)
    {
        if(cur==nums.size())
            return 0;
        int on_include=0;
        //If we are greater than previous length we add to the length of subsequence
        if(nums[cur]>prev)
            on_include=helper(nums,nums[cur],cur+1)+1;
        //Even if we are not there must be an increasing subsequence
        int on_ignore=0;
        on_ignore=helper(nums,prev,cur+1);
        return(max(on_include,on_ignore));
    }
public:
    int lengthOfLIS(vector<int>& nums) 
    {
     int max=helper(nums,-1,0);
        return max;    
    }
};

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

N (n ^ 2) የት N የድርድር መጠን ነው። እዚህ እኛ ወደ O (N * N) የጊዜ ውስብስብነት የሚወስደንን ሁለት ቀለበቶችን እናካሂዳለን ፡፡

የቦታ ውስብስብነት

ኦ (1) ምክንያቱም እኛ ወደ ተለዋዋጭ ቦታ c0mplexity የሚወስደንን አንዳንድ ተለዋዋጮችን እንጠቀማለን።

አቀራረብ 2: ተለዋዋጭ ፕሮግራም

ለ [9 ፣ 2 ፣ 5 ፣ 3 ፣ 7 ፣ 10 ፣ 8 ፣ 7] ረጅሙን እየጨመረ ያለውን ቀጣይነት እናገኝ ፡፡

  • የ “ኢንቲጀር ድርድር” መጠን ድርድር እንፍጠር
  • እያንዳንዱ ንጥረ ነገር ቢያንስ የአንድ ርዝመት ተከታይ ነው ማለትም ቁጥሮች እራሳቸው ስለሆነም ድርድርን በአንዱ ያስጀምሩታል።
    11111111
  • ለእያንዳንዱ የኢሽ አቋም ፣ ከእሱ በፊት ያለውን የ jth አቀማመጥ እንመለከታለን
  • አንድ [j]
  • ለ i = 2 ፣ ለተመሳሳይ i = 0 እና i = 1 በኩል እንመለከታለን ፡፡ ከቀዶ ጥገናዎቹ በኋላ የተሻሻለውን ድርድር እንመልከት
    11ከፍተኛ (j + 1, i)

    (2)

    11111
  • ከሁሉም ንፅፅሮች በኋላ የመጨረሻው ድርድር እንደ ሊታይ ይችላል-
    11223443
  • የሁሉንም ቁጥሮች ከፍተኛውን ለማግኘት የከፍተኛው ቀጣይ ርዝመት ምን ያህል እንደሆነ እናገኛለን 4. ይህንን በተሻለ በኮድ እንረዳው ፡፡

የጃቫ ፕሮግራም ረዘም ላለ ጊዜ ለሚቀጥለው ውጤት

class Solution 
{
    public int lengthOfLIS(int[] nums) 
    {
        int ans[]=new int[nums.length];
        for(int i=0;i<ans.length;i++)
            ans[i]=1;
        for(int i=1;i<nums.length;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(nums[i]>nums[j])
                {ans[i]=Math.max(ans[i],(ans[j]+1));}
            }
        }
        int max=0;
        for(int i=0;i<ans.length;i++)
        {
            max=Math.max(ans[i],max);
        }
        return max;
    }
}

C ++ ፕሮግራም ረዘም ላለ ጊዜ ለሚጨምር

class Solution 
{
public:
    int cmax(int a,int b)
    {
        if(a>b)
            return a;
        else
            return b;
    }
public:
    int lengthOfLIS(vector<int>& nums) 
    {
    int ans[nums.size()];
    int i,j;
        for(i=0;i<nums.size();i++)
            ans[i]=1;
        for(i=1;i<nums.size();i++)
        {
            for(j=0;j<i;j++)
            {
                if(nums[i]>nums[j])
                {ans[i]=cmax(ans[i],(ans[j]+1));}
            }
        }
        int max=0;
        for(int i=0;i<nums.size();i++)
        {
            max=cmax(ans[i],max);
        }
        return max; 
    }
};

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ከላይ ያለው መፍትሔ የጊዜ ውስብስብነት O (n ^ 2) ነው።

የቦታ ውስብስብነት

ኦ (n) ምክንያቱም ከእያንዳንዱ መረጃ ጠቋሚ በኋላ መልሱን ለማከማቸት አንድ ድርድር እንጠቀማለን።

ማጣቀሻዎች