力扣最热一百题——最大子数组和

目录

题目链接：53. 最大子数组和 - 力扣（LeetCode）

题目描述

示例

提示：

解法一：动态规划

举例分析

时间复杂度

Java写法：

C++写法：

优化

总结

---

题目链接：53. 最大子数组和 - 力扣（LeetCode）

注：下述题目描述和示例均来自力扣

题目描述

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

子数组

是数组中的一个连续部分。

示例

示例 1：

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

示例 2：

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

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

提示：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104

---

解法一：动态规划

1. 初始化：

   • 首先，获取数组 nums 的长度 len。
   • 新建一个数组 ap，这个数组用于存储到达每个索引 i 时，包含该元素的最大连续子数组和。
   • 初始化 ap[0] 为 nums[0]，因为第一个元素的最大子数组和只能是它本身。
   • 初始化 res 为 ap[0]，用来存储最终的最大子数组和。

2. 动态规划计算：

   • 从 i = 1 开始遍历整个数组：
     • 对于每个 i，计算 ap[i]：
       • ap[i - 1] + nums[i] 表示将当前元素 nums[i] 加入到前一个位置 i-1 的最大子数组和中。
       • nums[i] 表示不加前面的子数组，直接以当前元素 nums[i] 作为新子数组的开始。
       • 取两者中的较大值作为 ap[i]，表示在 i 位置时的最大子数组和。
     • 更新 res 为当前最大值，res = Math.max(res, ap[i])。

3. 返回结果：

   • 最后，返回 res，即数组中最大子数组和。

举例分析

假设 nums = [-2,1,-3,4,-1,2,1,-5,4]，每一步的计算如下：

• i = 0，ap[0] = -2，res = -2
• i = 1，ap[1] = max(-2 + 1, 1) = 1，res = max(-2, 1) = 1
• i = 2，ap[2] = max(1 + -3, -3) = -2，res = max(1, -2) = 1
• i = 3，ap[3] = max(-2 + 4, 4) = 4，res = max(1, 4) = 4
• i = 4，ap[4] = max(4 + -1, -1) = 3，res = max(4, 3) = 4
• i = 5，ap[5] = max(3 + 2, 2) = 5，res = max(4, 5) = 5
• i = 6，ap[6] = max(5 + 1, 1) = 6，res = max(5, 6) = 6
• i = 7，ap[7] = max(6 + -5, -5) = 1，res = max(6, 1) = 6
• i = 8，ap[8] = max(1 + 4, 4) = 5，res = max(6, 5) = 6

最终结果为 6，即最大子数组和是 [4, -1, 2, 1]，和为 6。

时间复杂度

• 时间复杂度为 O(n)，因为我们只需要遍历数组一次。
• 空间复杂度为 O(n)，因为我们使用了额外的 dp 数组来存储每一步的计算结果。

---

Java写法：

class Solution {public int maxSubArray(int[] nums) {int len = nums.length;// 新建一个dp数组// dp[i]表示索引0到i这个位置的最大连续子数组的值int[] ap = new int[len] ;// 初始化dp数组ap[0] = nums[0];int res = ap[0];   // -2,1,-3,4,-1,2,1,-5,4// -2-1 -3 4 3  5 6 1  5for(int i = 1;i < len;i++){// 如果当前位置的值加上前一个位置的最大连续子数组的和大就要这个// 否则就存入当前位置的值ap[i] = Math.max(ap[i - 1] + nums[i],nums[i]);// 更新res的值res = Math.max(res,ap[i]);}return res;}
}

C++写法：

class Solution {
public:int maxSubArray(vector<int>& nums) {int len = nums.size();// 定义出dp数组vector<int> dp(len);// 初始化dp[0] = nums[0];int res = dp[0];for(int i = 1;i < len; i++){dp[i] = max(dp[i - 1] + nums[i],nums[i]);res = max(res,dp[i]);}return res;}
};

---

优化

        这里其实我们每次只需要一个之前存储的值，因此我们完全不需要使用数组来存储全部的值，我们只需要每次维护i-1的位置的值就行了。

Java：

class Solution {public int maxSubArray(int[] nums) {int dp = nums[0];int res = dp;   for(int i = 1;i < nums.length;i++){dp = Math.max(dp + nums[i],nums[i]);// 更新res的值res = Math.max(res,dp);}return res;}
}

打败了全世界的人！！！！！！！！！！！！！ 

C++：

class Solution {
public:int maxSubArray(vector<int>& nums) {int dp = nums[0];int res = dp;for(int i = 1;i < nums.size(); i++){dp = max(dp + nums[i],nums[i]);res = max(res,dp);}return res;}
};

---

总结

        

        这段代码实现了求解数组最大子数组和的问题，通过动态规划的方式逐步计算包含每个元素的最大子数组和。主要步骤包括：

1. 初始化：创建一个数组 ap，存储每个位置的最大子数组和，并初始化第一个元素的值。

2. 动态规划：遍历数组，每次计算当前元素的最大子数组和，比较当前值与加入前一个位置最大和后的值，选择较大者存入 ap。同时，更新全局最大值 res。

3. 返回结果：最终返回最大子数组和 res。

时间复杂度为 O(n)，空间复杂度为 O(n)。