Максимално решение на Subarray Leetcode  


Ниво на трудност Лесно
Често задавани в Кирпич Амазонка ябълка Bloomberg ByteDance Cisco Facebook Goldman Sachs Google JPMorgan LinkedIn Microsoft Оракул 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:
Max subarray лежи изцяло в лявата половина на масива.
Дело 2:
Max subarray лежи изцяло в дясната половина на масива.
Дело 3:
Частична част от максималния подмасив лежи в лявата половина, а друга част от него лежи във втората половина (т.е. подмасивът пресича средния елемент на масива)

Както виждаме, случай 1 и случай 2 в основата си са подпроблема на масив с размер N / 2, имащ същата дефиниция като основния проблем. Където N е размерът на текущия масив. Така че можем просто повтаря се функцията над две половини на масива.
Сега основната част е случай 3, който трябва да разрешим в текущата функция и след това можем да върнем максималната сума от тези 3 случая.

Вижте също
Брой братя и сестри на даден възел в n-ary Tree

Нека видим как можем да разрешим случай 3:

Да предположим, че имаме масив = [-2,1, -3,4, -1,2,1, -5,4]
Намираме средния индекс, за да го разделим на две равни половини.
среден индекс = (0 + 9) / 2 = 4

Максимално решение на Subarray Leetcode

Както случай 3 казва, че максималната сума ще пресече средния елемент. Затова ще се опитаме да намерим максималната сума, започваща в средата и завършваща вляво. По същия начин ще намерим максималната сума, започваща от (mid + 1) и завършваща от дясната страна. По този начин ще намерим максималния подмасив, който пресича средната граница за случай 3.

алгоритъм:

  • Разделете масива на две половини.
  • Рекурсивно намерете максималната сума на подмасива за левия подмасив.
  • Рекурсивно намерете максималната сума на подмасива за десния подмасив.
  • Намерете максималната сума на подмасив, която пресича средната точка.
  • Върнете максимума от над три суми.

Внедряване за максимално решение на Subarray 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

Анализ на сложността за максимално решение на Subarray Leetcode

Сложност във времето

O (NlogN): В действителност, разделяй и владей, разделяме проблема на две равни половини с размер N / 2. Отново се дели по размер на N / 4 и т.н. Следователно най-дълбокото ниво на рекурсия ще бъде logN, където размерът на масива ще бъде 1 и ние се връщаме от там. На всяко ниво изпълняваме задача O (n), следователно общата времева сложност ще бъде O (NlogN). Тук връзката на рецидивите е

Вижте също
Добавяне и търсене на Word - Дизайн на структурата на данни LeetCode

Сложност на пространството 

O (logN): logN пространство се използва за стека на рекурсия.

 

Подход 2 (метод на Kadane)  

Методът на Kadane е известен алгоритъм за суми от под масив. В този метод ние просто итерираме веднъж върху дадения входен масив. Вземаме текуща сума първоначално със стойност нула и добавяме всеки елемент в пътя. Добавяме всеки елемент към текущата сума, ако предишната текуща сума не е отрицателна или по друг начин просто прекъсваме непрекъснатостта и актуализираме текущата сума с текущ елемент. Заедно с това на всяка позиция проверяваме дали текущата сума също е глобален максимум или не и актуализираме глобалния максимум според това.

алгоритъм:

  • Създайте променлива за съхраняване на глобален максимум. Инициализирайте с най-отрицателно число (INT_MIN).
  • Създайте променлива за съхраняване на текущата сума. Инициализирайте с нула.
  • Изпълнете цикъл отляво надясно над масива. Ако текущата сума е станала отрицателна, актуализирайте я със стойност 0.
  • Добавете текущия елемент към текущата сума и актуализирайте глобалния максимум, ако текущата сума е по-голяма от глобалния максимум.
  • Върнете глобалния максимум.

Внедряване за максимално решение на Subarray 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

Анализ на сложността за максимално решение на Subarray Leetcode

Сложност във времето

НА) : Тъй като това е еднопроходен алгоритъм върху масива.

Вижте също
Три последователни шанса Leetcode решение

Сложност на пространството 

O (1): Не се използва допълнителна памет.

1