最大子阵列Leetcode解决方案  


难度级别 易得奖学金
经常问 土砖 亚马逊 Apple 彭博 ByteDance 思科 Facebook 高盛 谷歌 摩根大通 LinkedIn 微软 神谕 贝宝 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): 不使用额外的内存。