Хамгийн урт нэмэгдэж буй үр дагавар


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Adobe Амазоны Citrix CodeNation Facebook-ийн Google-ийн Microsoft- Samsung Zoho
Хоёртын хайлт Динамик програмчлал Лис

Бидэнд массив бүхэл тоонууд нь ангилагдаагүй бөгөөд бид хамгийн урт дарааллыг олох ёстой.

  • Дараалал дараалсан байх шаардлагагүй
  • Дараалал улам бүр нэмэгдэж байна

Үүнийг цөөн хэдэн жишээн дээр илүү сайн ойлгоцгооё.

Жишээ нь

Оролт

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

гаралтын

4

Тайлбар

Хамгийн урт нэмэгдэж буй дараагийн дараалал бол [2,3,7,10].

Хандалт 1: Харгис хүчин

Энэ арга нь бүх боломжит дэд хэсгүүдийг судалж, мөн чанараараа улам бүр нэмэгдэж буй хамгийн урт дарааллыг олох явдал юм.

Одоо бид массив дахь бүхэл тоогоор зочлох бүрт хоёр тохиолдол байж болно.

  • Үүнийг дараалалд оруулж болно, өөрөөр хэлбэл өмнөх элементээс том байна
  • Энэ нь өмнөх элементээс бага хэмжээтэй тул дэд хэсэгт оруулах боломжгүй юм

Гэхдээ тухайн элементийг тодорхой байрлалд оруулсан эсэхээс үл хамааран тодорхой уртын тухайн цэг хүртэл нэмэгдэж буй дэд дараалал байгаа бөгөөд бид хамгийн их уртыг тэр цаг хугацаанд буцааж өгч чадна. Үүнийг кодын хэсэг (Java ба C ++ дээр) илүү сайн ойлгоорой.

Хамгийн урт үр дагаварт хүргэх Java хөтөлбөр

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;    
    }
};

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (n ^ 2), энд N нь массивын хэмжээ юм. Энд бид гогцоонуудын хувьд хоёрыг ажиллуулдаг бөгөөд энэ нь O (N * N) цагийн нарийн төвөгтэй байдалд хүргэдэг.

Сансрын нарийн төвөгтэй байдал

O (1), учир нь бид зарим хувьсагчийг ашигладаг бөгөөд энэ нь биднийг орон зайг тогтмол байлгахад хүргэдэг.

Хандалт 2: Динамик програмчлал

[9, 2, 5, 3, 7, 10, 8, 7] -н хамгийн урт өсөх дарааллыг олъё.

  • Бүхэл массивын хэмжээтэй массивыг бүтээцгээе
  • Элемент бүр нь дор хаяж нэг урттай дараалал бөгөөд өөрөөр хэлбэл тоонууд нь массивыг нэгээр эхлүүлнэ.
    1 1 1 1 1 1 1 1
  • Бүх ith байрлал бүрийн хувьд бид өмнө байрласан j байр суурийг хардаг
  • Хэрэв [j]
  • I = 2-ийн хувьд бид i = 0 ба i = 1-ийг ижил байдлаар харна. Үйлдлүүдийн дараа өөрчлөгдсөн массивыг авч үзье
    1 1 Макс (j + 1, i)

    (2)

    1 1 1 1 1
  • Бүх харьцуулалтын дараахь массивыг дараах байдлаар авч үзэж болно.
    1 1 2 2 3 4 4 3
  • Бүх тоонуудаас хамгийн их тоог олох нь хамгийн их дарааллын уртыг 4. байх болно. Үүнийг кодоор илүү сайн ойлгоё.

Хамгийн урт үр дагаварт хүргэх Java хөтөлбөр

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) юм.

Сансрын нарийн төвөгтэй байдал

O (n), учир нь бид хариултыг индекс бүрийн дараа хадгалах массивыг ашигладаг.

Ашигласан материал