Максимално решение за под-низа Leetcode


Ниво на тешкотија Лесно
Често прашувано во Adobe Амазон Јаболко Блумберг ByteDance Cisco Facebook Голдман Сакс Google JPMorgan Скопје Мајкрософт Oracle PayPal Исплата Uber
Низа Подели и освои Динамичко програмирање

Изјава за проблем

Со оглед на бројки од низа целови, пронајдете го соседниот под-низа (што содржи барем еден број) кој има најголема сума и вратете го својот збир.

пример

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 случаи.

Ајде да видиме како можеме да решиме за случајот 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

Анализа на сложеност за максимално решение за леткод на под-низа

Временска комплексност

О (NlogN): Подели и победи, всушност, го делиме проблемот на две еднакви половини со големина N / 2. Повторно се дели во големина на N / 4 и така натаму. Оттука, најдлабокото ниво на повторување ќе биде најавено каде големината на низата ќе биде 1 и ние се враќаме оттаму. На секое ниво, ние правиме задача O (n), затоа вкупната временска сложеност ќе биде O (NlogN). Тука е релацијата на повторување

Комплексноста на просторот 

О (најаваН): 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

Анализа на сложеност за максимално решение за леткод на под-низа

Временска комплексност

НА) : Бидејќи тој е алгоритам за едно поминување над низата.

Комплексноста на просторот 

О (1): Не се користи дополнителна меморија.