[面试精选] 0053. 最大子数组和

1. 题目链接


53. 最大子数组和 - 力扣（LeetCode）


2. 题目描述


给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包罗一个元素），返回其最大和。
子数组是数组中的一个连续部门。


3. 题目示例


   示例 1 :

1. 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
2. 输出：6
3. 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

复制代码

   示例 2 :

1. 输入：nums = [1]
2. 输出：1

复制代码

4. 解题思绪

• 问题理解：
  
  
  
  • 给定一个整数数组 nums，需要找到一个连续子数组，使得其和最大，并返回这个最大和。
    
  
  
• 关键思绪：
  
  
  
  • 动态规划：使用动态规划的思想，通过遍历数组，渐渐计算以当前元素结尾的最大子数组和。
    
  • 状态转移：对于当前元素 nums，假如前面的子数组和 nums[i-1] 大于0，则将其加到 nums 上，否则从 nums 重新开始计算子数组和。
    
  
  
• 算法流程：
  
  
  
  • 初始化最大和 res 为数组的第一个元素。
    
  • 从第二个元素开始遍历数组：
    
    
    
    • 更新 nums 为 nums + max(nums[i-1], 0)，即假如前面的子数组和对当前元素有增益结果，则加上前面的子数组和。
      
    • 更新 res 为当前最大值。
      
    
    
  • 返回 res。
    
  
  

5. 题解代码

1. class Solution {
2.     public int maxSubArray(int[] nums) {
3.         // 初始化结果为数组的第一个元素
4.         int res = nums[0];
5.         
6.         // 从第二个元素开始遍历数组
7.         for(int i = 1; i < nums.length; i++){
8.             // 当前元素的值加上前一个元素的值（如果前一个元素的值大于0）
9.             // 这相当于判断是否要延续前面的子数组
10.             nums[i] += Math.max(nums[i-1], 0);
11.             
12.             // 更新结果为当前最大值
13.             res = Math.max(res, nums[i]);
14.         }
15.         
16.         // 返回最大子数组和
17.         return res;
18.     }
19. }

复制代码

6. 复杂度分析

• 时间复杂度：
  
  
  
  • 遍历数组一次，时间复杂度为 O(n)，其中 n 是数组的长度。
    
  
  
• 空间复杂度：
  
  
  
  • 在原数组上举行修改，没有使用额外的空间，空间复杂度为 O(1)。