最大子陣列Leetcode解決方案  


難度級別 容易獎學金
經常問 土磚 亞馬遜 蘋果 彭博社 ByteDance 思科 Facebook 高盛 谷歌 摩根大通 LinkedIn Microsoft微軟 神諭 貝寶 Paytm 尤伯杯
算法 排列 編碼 分而治之 動態編程 訪問 面試準備 力碼 力碼解決方案

問題陳述  

給定一個整數數組nums,找到相鄰的 子陣列 (包含至少一個數字),且總和最大,並返回其總和。

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

說明:

[4,-1,2,1]的總和= 6。

nums = [-1]
-1

方法1(分而治之)  

在這種方法中,我們將討論分而治之的技術來解決這個問題。 我們試圖找到具有最大和的連續子數組。 因此,可以說最優子陣列可以位於陣列的任何部分。 因此,我們提出了三種情況,涵蓋了所有可能性:

案例1:
最大子數組完全位於數組的左半部分。
案例2:
Max子數組完全位於數組的右半部分。
案例3:
max子數組的部分位於左半部分,另一部分位於後半部分(即子數組與數組的中間元素交叉)

如我們所見,情況1和情況2基本上是N / 2大小的數組的一個子問題,具有與主要問題相同的定義。 其中N是當前數組的大小。 所以我們可以簡單地 重複發生 函數超過數組的兩半。
現在主要部分是情況3,我們必須在當前函數中對其進行求解,然後才能從這3個情況中返回最大和。

也可以看看
n元樹中給定節點的同級數

讓我們看看如何解決情況3:

假設我們有數組= [-2,1,-3,4,-1,2,1,-5,4]
我們找到中間指數將其分為兩個相等的兩半。
中索引=(0 + 9)/ 2 = 4

最大子陣列Leetcode解決方案

就像情況3所說的那樣,最大和將越過中間元素。 因此,我們將嘗試找到從中間開始到左側結束的最大和。 同樣,我們將找到從(mid + 1)開始到右側結束的最大和。 這樣,我們將找到情況3的越過中間邊界的max子數組。

算法:

  • 將陣列分為兩半。
  • 遞歸地找到左子數組的最大子數組總和。
  • 遞歸地找到右子數組的最大子數組總和。
  • 查找穿過中點的最大子數組總和。
  • 返回上述三個總和的最大值。

最大子陣列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)。 這裡的遞歸關係是

也可以看看
添加和搜索Word-數據結構設計LeetCode

空間複雜度 

O(logN): logN空間用於遞歸堆棧。

 

方法2(Kadane方法)  

Kadane的方法是子數組求和的著名算法。 在這種方法中,我們只需在給定的輸入數組上迭代一次。 我們首先獲取一個當前總和,其值為零,然後將路徑中的每個元素相加。 如果先前的當前總和不為負,則將每個元素加到當前總和上,否則我們將破壞連續性並使用當前元素更新當前總和。 連同它在每個位置處,我們檢查當前總和是否也是全局最大值,並據此更新全局最大值。

算法:

  • 創建一個變量來存儲全局最大值。 用最大負數(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解決方案的複雜度分析

時間複雜度

上) : 由於它是對數組的一遍算法。

也可以看看
三個連續賠率Leetcode解決方案

空間複雜度 

O(1): 不使用額外的內存。