Хамгийн дээд дэд схемийн Leetcode шийдэл  


Хэцүү байдлын түвшин Easy
Байнга асуудаг Adobe Амазоны Apple-ийн Bloomberg БайтДанс Cisco Facebook-ийн Goldman Sachs Google-ийн JPMorgan LinkedIn Microsoft- Oracle-ийн PayPal Paytm Uber
алгоритмууд Array кодлох Хуваагаад, ялж байна Динамик програмчлал ярилцлага ярилцлагын бэлтгэл LeetCode LeetCodeSolutions

Асуудлын мэдэгдэл  

Бүхэл тоон массивын дугаар өгөгдсөн бол зэргэлдээх хэсгийг ол дэд хэсэг хамгийн бага нийлбэртэй бөгөөд нийлбэрийг нь буцааж өгөх (дор хаяж нэг тоо агуулсан).

Жишээ нь

nums = [-2,1,-3,4,-1,2,1,-5,4]
6

Тайлбар:

[4, -1,2,1] хамгийн том нийлбэр = 6 байна.

nums = [-1]
-1

Хандалт 1 (Хувааж, байлдан дагуулах)  

Энэ хандлагаар бид энэ асуудлыг шийдэх хуваах, байлдан дагуулах арга техникийг ярилцах болно. Хамгийн их нийлбэртэй зэргэлдээ дэд мөрийг олохыг хичээж байна. Тиймээс хамгийн оновчтой дэд массив нь массивын аль ч хэсэгт байж болно гэж хэлж болно. Тиймээс бид бүх тохиолдлыг хамарсан гурван тохиолдлыг гаргаж байна.

Тохиолдол 1:
Макс дэд массив нь массивын зүүн хагаст бүрэн байрладаг.
Тохиолдол 2:
Макс дэд массив нь массивын баруун хагаст байрладаг.
Тохиолдол 3:
Макс дэд массивын хэсэгчилсэн хэсэг нь зүүн хагаст, нөгөө хэсэг нь хоёрдугаар хагаст байрлана (өөрөөр хэлбэл дэд массив нь массивын дунд элементийг гаталж байна)

1-р тохиолдол, 2-р тохиолдол нь үндсэндээ N / 2 хэмжээтэй массивын гол асуудалтай ижил тодорхойлолттой дэд асуудал юм. N бол одоогийн массивын хэмжээ. Тиймээс бид хялбархан хийж чадна давтана массивын хоёр талаас дээш функц.
Одоо гол хэсэг нь одоогийн функцэд шийдвэрлэх ёстой 3-р тохиолдол бөгөөд бид эдгээр 3 тохиолдлоос хамгийн их нийлбэрийг буцааж өгөх болно.

мөн үзнэ үү
N-ary мод дахь өгөгдсөн зангилааны ах дүүгийн тоо

3-р хэргийг хэрхэн шийдэж болохыг харцгаая.

Бид = [-2,1, -3,4, -1,2,1, -5,4] массивтай гэж бодъё.
Үүнийг хоёр тэнцүү хагаст хуваах дунд индексийг олдог.
дунд индекс = (0 + 9) / 2 = 4

Хамгийн дээд дэд схемийн Leetcode шийдэл

3-р тохиолдол нь хамгийн их нийлбэр дунд элементийг гатлах болно гэж хэлж байна. Тиймээс бид хамгийн дээд нийлбэрийг дундаас эхлээд зүүн талаас нь олохыг хичээх болно. Үүний нэгэн адил бид хамгийн их нийлбэрийг (дунд + 1) -ээс эхэлж, баруун талд нь олох болно. Ийм байдлаар бид 3-р тохиолдлын дунд хилийг давах хамгийн дээд дэд массивыг олох болно.

Алгоритм:

  • Массивыг хоёр хэсэгт хуваа.
  • Зүүн дэд массивын хамгийн дээд дэд нийлбэрийг давтана.
  • Баруун дэд массивын хамгийн дээд дэд нийлбэрийг давтана.
  • Дундаж цэгийг гатлах хамгийн дээд дэд нийлбэрийг ол.
  • Хамгийн дээд гурван нийлбэрийг буцаана уу.

Доод түвшний Leetcode шийдлийн хамгийн дээд түвшний шийдэл

C ++ програм

#include <bits/stdc++.h>
using namespace std;

int helper(int i,int j, vector<int>& nums)
{
    if(i==j) return nums[i];
    int left_cross=INT_MIN, right_cross=INT_MIN;

    int mid= (i+j)/2;
    int cur=0;
    for(int k=mid+1;k<=j;k++)
    {
        cur+= nums[k];
        right_cross= max(right_cross,cur);
    }

    cur=0;
    for(int k=mid;k>=i;k--)
    {
        cur+= nums[k];
        left_cross= max(left_cross,cur);
    }

    int cross_sum = left_cross + right_cross;
    int left_sum  = helper(i,mid,nums);
    int right_sum = helper(mid+1,j,nums);

    return max( cross_sum , max(left_sum , right_sum) );
}

int maxSubArray(vector<int>& nums) {
    return helper(0,nums.size()-1,nums);
}

int main() 
{
    vector<int> nums={-2,1,-3,4,-1,2,1,-5,4};
    cout<< maxSubArray(nums) <<endl;
    return 0; 
}
6

Java програм

class Rextester{
    
  static int helper(int i,int j, int[] nums)
    { 
        if(i==j) return nums[i];       
        int left_cross=Integer.MIN_VALUE, right_cross=Integer.MIN_VALUE;
        
        int mid= (i+j)/2;
        int cur=0;
        for(int k=mid+1;k<=j;k++)
        {
            cur+= nums[k];
            right_cross= Math.max(right_cross,cur);
        }
        
        cur=0;
        for(int k=mid;k>=i;k--)
        {
            cur+= nums[k];
            left_cross= Math.max(left_cross,cur);
        }
        
        int cross_sum=  left_cross + right_cross; 
        int left_sum = helper(i,mid,nums);
        int right_sum = helper(mid+1,j,nums);
        
        return Math.max( cross_sum , Math.max(left_sum , right_sum) );        
    }
    
    public static int maxSubArray(int[] nums) {
        return helper(0,nums.length-1,nums);
    }
    
  public static void main(String args[])
    {
       	int[] nums={-2,1,-3,4,-1,2,1,-5,4};
    System.out.println(maxSubArray(nums));
    }
}
6

Хамгийн дээд дэд дэд массивын Leetcode шийдлийн нарийн төвөгтэй байдлын шинжилгээ

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

O (NlogN): Бид хувааж, байлдан дагуулахын тулд асуудлыг N / 2 хэмжээтэй хоёр тэнцүү хагаст хувааж байна. Дахин хэлэхэд энэ нь N / 4 хэмжээтэй хуваагдана гэх мэт. Тиймээс рекурсийн хамгийн гүн түвшин нь logN байх бөгөөд массивын хэмжээ 1 байх бөгөөд бид тэндээс буцаж ирнэ. Түвшин бүрт бид O (n) даалгавар гүйцэтгэж байгаа тул цаг хугацааны нийт төвөгтэй байдал O (NlogN) болно. Энд давтагдах хамаарал байна

мөн үзнэ үү
Үг нэмэх ба хайх - Мэдээллийн бүтцийн дизайн LeetCode

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

O (logN): logN зай нь рекурсын стек хийхэд ашиглагддаг.

 

Хандлага 2 (Каданегийн арга)  

Каданегийн арга бол дэд массивын нийлбэрийн алдартай алгоритм юм. Энэ аргаар бид өгөгдсөн оролтын массив дээр нэг удаа давтана. Эхлээд тэг утгатай гүйдлийн нийлбэрийг аваад зам дээрх элемент бүрийг нэмнэ. Өмнөх одоогийн нийлбэр нь сөрөг биш эсвэл өөр тохиолдолд бид үргэлжлэлийг эвдэж одоогийн нийлбэрийг шинэчилнэ. Үүний зэрэгцээ байрлал бүрт бид одоогийн нийлбэр нь дэлхийн хамгийн их мөн эсэхийг шалгаж, дэлхийн хамгийн дээд хэмжээг шинэчилнэ.

Алгоритм:

  • Глобал дээд хэмжээг хадгалах хувьсагч үүсгэ. Хамгийн сөрөг тоогоор эхлүүлэх (INT_MIN).
  • Одоогийн нийлбэрийг хадгалах хувьсагч үүсгэх. Тэгээр эхлүүлнэ.
  • Массивын дээгүүр зүүнээс баруун тийш гогцоо ажиллуулна уу. Хэрэв одоогийн нийлбэр сөрөг болсон бол түүнийг 0 гэсэн утгатай шинэчил.
  • Одоогийн нийлбэр дээр одоогийн элементийг нэмж, хэрэв одоогийн нийлбэр нь дэлхийн дээд хэмжээнээс их байвал дэлхийн дээд хэмжээг шинэчилнэ.
  • Дэлхийн хамгийн дээд хэмжээг буцаана уу.

Доод түвшний Leetcode шийдлийн хамгийн дээд түвшний шийдэл

C ++ програм

#include <bits/stdc++.h>
using namespace std;

int maxSubArray(vector<int>& nums) 
{
    int max_sum=INT_MIN;
    int cur=0;
    for(auto x:nums)
    {
        if(cur<0) cur=0;
        cur += x;
        max_sum =  max(max_sum , cur);
    }
    return max_sum;
}

int main() 
{
    vector<int> nums={-2,1,-3,4,-1,2,1,-5,4};
    cout<< maxSubArray(nums) <<endl;
    return 0; 
}
6

Java програм

class Rextester{
  
    public static int maxSubArray(int[] nums) 
    {
        int max_sum = Integer.MIN_VALUE;
        int cur=0;
        for(int x:nums)
        {
            if(cur<0) cur=0;
            cur += x;
            max_sum =  Math.max(max_sum , cur);
        }
        return max_sum;
    }
    
  public static void main(String args[])
    {
       	int[] nums={-2,1,-3,4,-1,2,1,-5,4};
    System.out.println(maxSubArray(nums));
    }
}
6

Хамгийн дээд дэд дэд массивын Leetcode шийдлийн нарийн төвөгтэй байдлын шинжилгээ

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

O (N): Энэ нь массивыг дамжуулах нэг алгоритм тул.

мөн үзнэ үү
Гурван дараалсан коэффициент бүхий Leetcode шийдэл

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

O (1): Нэмэлт санах ой ашигладаггүй.

1