Ҳалли максималии Subarray Leetcode Solution  


Сатҳи душворӣ осон
Аксар вақт пурсида мешавад Adobe Amazon себ Блумберг ByteDance Cisco Facebook Голдман Sachs Google JPMorgan LinkedIn Microsoft Oracle PayPal Пардохт Uber
алгоритмҳо тартиботи ҳарбӣ рамзгузорӣ Тақсим кунед ва ғолиб шавед Барномарезии динамикӣ мусоҳиба омодасозии мусоҳиба LeetCode LeetCodeSolutions

Изҳороти мушкилот  

Бо назардошти ададҳои массиви бутун, ҳамҷояро ёбед зеркашӣ (дорои ҳадди аққал як рақам), ки маблағи калонтарин дорад ва маблағи онро бармегардонад.

мисол

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

Шарҳ:

[4, -1,2,1] суммаи аз ҳама калон = 6 дорад.

nums = [-1]
-1

Равиши 1 (тақсим кунед ва ғолиб кунед)  

Дар ин равиш, мо дар бораи тақсим ва фатҳи техникаи ҳалли ин масъала баҳс хоҳем кард. Мо кӯшиш менамоем, ки зергурӯҳи ҳамсояро, ки ҳадди аксар маблағ дорад, пайдо кунем. Аз ин рӯ, мо гуфта метавонем, ки зеркатри оптималӣ метавонад дар ягон қисми массив ҷойгир бошад. Ҳамин тавр, мо се ҳолат месозем, ки ҳамаи имконотро фаро мегиранд:

Мисоли 1:
Максимум subarray комилан дар нимаи чапи массив ҷойгир аст.
Мисоли 2:
Максимум subarray пурра дар нимаи рости массив ҷойгир аст.
Мисоли 3:
Қисми қисмати максимум дар нимаи чап ва қисми дигари қисми он дар нимаи дуввум ҷойгиранд (яъне subarray ин унсури миёнаи массивро убур мекунад)

Чӣ тавре ки мо мебинем, ки ҳолати 1 ва парвандаи 2 асосан як зерпроблемаи массиви N / 2 мебошад, ки таърифи он бо мушкилоти асосӣ баробар аст. Дар куҷо N андозаи массиви ҷорӣ аст. Пас, мо метавонем танҳо такрор мекунад вазифаи зиёда аз ду нимаи массив.
Ҳоло қисми асосӣ ҳолати 3 мебошад, ки мо бояд онро дар вазифаи ҳозира ҳал кунем ва пас мо метавонем аз ин 3 ҳолат маблағи максималиро баргардонем.

ҳамчунин нигаред
Шумораи хоҳарони гиреҳи додашуда дар дарахти n-ary

Биёед бубинем, ки чӣ гуна мо метавонем барои парвандаи 3 ҳал кунем:

Фарз мекунем, ки мо массиви = [-2,1, -3,4, -1,2,1, -5,4]
Мо шохиси миёнаро пайдо мекунем, то онро ба ду ним баробар тақсим кунем.
индекси миёна = (0 + 9) / 2 = 4

Ҳалли максималии Subarray Leetcode Solution

Дар ҳолати 3 гуфта мешавад, ки ҳадди аксар миқдори унсури миёнаро убур хоҳад кард. Ҳамин тавр, мо кӯшиш хоҳем кард, ки маблағи максимумро аз миёна сар карда, дар тарафи чап ба поён расем. Ба ҳамин монанд, мо миқдори максимумро аз (миёнаи + 1) сар карда, дар тарафи рост хотима хоҳем ёфт. Бо ин роҳ мо максимум subarray-ро, ки сарҳади миёнаро барои парвандаи 3 убур мекунад, пайдо мекунем.

Алгоритм:

  • Массивро ба ду қисм тақсим кунед.
  • Маблағи ҳадди зерзерро барои ҷудоихоҳи чап рекурсивӣ ёбед.
  • Маблағи ҳадди зерзерро барои ҷуброни рост ба таври рекурсивӣ ёбед.
  • Маблағи ҳадди зерсохторро, ки нуқтаи миёнаро убур мекунад, ёбед.
  • Максимум аз се сумро баргардонед.

Татбиқи Solution Maximum Subarray Leetcode Solution

Барномаи 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

Таҳлили мураккабӣ барои ҳалли максималии Subarray Leetcode Solution

Мураккабии вақт

О (NlogN): Ҳангоми тақсим кардан ва ғалаба кардан мо воқеан масъаларо ба ду қисмати баробари андозаи N / 2 тақсим мекунем. Боз он ба андозаи N / 4 тақсим мешавад ва ғайра. Аз ин рӯ, сатҳи амиқи рекурсия logN хоҳад буд, ки андозаи массив 1 хоҳад буд ва мо аз он ҷо бармегардем. Дар ҳар сатҳе, ки мо вазифаи O (n) -ро иҷро карда истодаем, аз ин рӯ мураккабии умумии вақт O (NlogN) хоҳад буд. Ин аст муносибати такрорӣ

ҳамчунин нигаред
Илова ва Ҷустуҷӯи Word - Тарроҳии сохтори маълумот LeetCode

Мураккабии фазо 

O (logN): фазои logN барои стеки рекурсия истифода мешавад.

 

Муносибати 2 (усули Кадане)  

Усули Кадане алгоритми машҳур барои sub array sum аст. Дар ин усул мо танҳо як маротиба дар массиви додашуда такрор мекунем. Мо маблағи ҷориро дар аввал бо арзиши сифр мегирем ва ҳар як элементро дар роҳ илова мекунем. Мо ҳар як унсурро ба суммаи ҷорӣ илова мекунем, агар ҳаҷми ҷории қаблӣ манфӣ набошад ё дар акси ҳол мо танҳо муттасилиро мешиканем ва ҳосили ҷориро бо унсури ҷорӣ нав мекунем. Дар баробари ин, дар ҳар як мавқеъ мо месанҷем, ки маблағи ҷорӣ низ ҳадди ҷаҳонӣ аст ё не ва ҳадди ҷаҳонро мувофиқи он навсозӣ мекунем.

Алгоритм:

  • Барои нигаҳдории максималии глобалӣ тағирёбанда эҷод кунед. Оғоз бо шумораи манфӣ (INT_MIN).
  • Барои нигоҳ доштани маблағи ҷорӣ тағирёбанда эҷод кунед. Оғоз бо сифр.
  • Доираро аз чап ба рост дар болои массив иҷро кунед. Агар маблағи ҷорӣ манфӣ шуда бошад, онро бо арзиши 0 навсозӣ кунед.
  • Элементи ҷориро ба суммаи ҷорӣ илова кунед ва ҳадди ҷаҳонро навсозӣ кунед, агар ҳаҷми ҷорӣ аз ҳадди ҷаҳонӣ зиёд бошад.
  • Максимум ҷаҳонро баргардонед.

Татбиқи Solution Maximum Subarray Leetcode Solution

Барномаи 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

Таҳлили мураккабӣ барои ҳалли максималии Subarray Leetcode Solution

Мураккабии вақт

О (Н): Азбаски ин як алгоритми гузариш аз болои массив аст.

ҳамчунин нигаред
Се модели пайдарпайи ҳалли Leetcode

Мураккабии фазо 

О (1): Ягон хотираи иловагӣ истифода намешавад.

1