当前位置：首页 > news >正文

力扣第五十三题——最大子数组和

news 来源：原创 2024/9/21 16:49:21

内容介绍

给你一个整数数组 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

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

完整代码

 int maxSubArray(int* nums, int numsSize) {int pre = 0, maxAns = nums[0];for (int i = 0; i < numsSize; i++) {pre = fmax(pre + nums[i], nums[i]);maxAns = fmax(maxAns, pre);}return maxAns;
}

思路详解

一、问题背景

给定一个整数数组，要求找到数组中的最大子数组和。所谓最大子数组和，是指数组中一个或多个连续元素组成的子数组，其元素之和最大。

二、解题思路

动态规划：
- 使用动态规划的思想，通过遍历数组，记录当前位置之前所有可能的子数组和，从而找到最大的子数组和。
状态定义：
- 定义一个变量pre来记录当前遍历到当前位置之前所有可能的子数组和的最大值。
- 初始时，pre为0，因为第一个元素本身就是最大的子数组和。
状态转移：
- 在遍历数组的过程中，对于每个元素，我们有两个选择：
  - 将当前元素与之前的子数组和pre相加，形成一个新的子数组和。
  - 只考虑当前元素，形成一个新的子数组和。
- 我们选择这两个子数组和中的较大者作为新的pre。
结果记录：
- 在遍历过程中，我们需要记录pre中的最大值，即当前找到的最大子数组和。
- 最终返回这个最大值。

三、代码详解

初始化：
- 初始化pre为0，表示当前还没有开始遍历数组。
- 初始化maxAns为数组的第一个元素，因为至少包含一个元素的子数组和的最大值就是数组的第一个元素。

int pre = 0, maxAns = nums[0];

遍历数组：
- 遍历数组中的每个元素。
- 对于每个元素，计算两种情况下的子数组和，并取较大者作为新的pre。
- 同时更新maxAns为pre和maxAns中的较大者。

for (int i = 0; i < numsSize; i++) {pre = fmax(pre + nums[i], nums[i]);maxAns = fmax(maxAns, pre);
}

返回结果：
- 遍历结束后，maxAns中存储的就是数组中的最大子数组和。
- 返回maxAns。

return maxAns;

四、总结

通过动态规划的思想，我们能够高效地找到数组中的最大子数组和。关键在于维护当前遍历到当前位置之前所有可能的子数组和的最大值，并在遍历过程中不断更新这个值。这种方法的时间复杂度为O(n)，空间复杂度为O(1)，因为只需要常数级别的额外空间。

知识点精炼

一、核心概念

动态规划：一种通过保存中间结果来避免重复计算的算法设计技巧。
状态转移：在动态规划中，每个状态都是基于前一个状态计算得出的。
贪心算法：一种在每一步选择中都采取当前状态下最优（即看起来最有利）的选择，从而希望导致全局最优解的算法。

二、知识点精炼

最大子数组和问题：
- 要求在数组中找到一个子数组，其元素之和最大。
动态规划解法：
- 使用一个变量pre来记录从数组开始到当前位置的所有可能的子数组和的最大值。
- 在遍历数组的过程中，更新pre为当前元素与pre相加的和以及当前元素的较大者。
状态转移：
- 在遍历数组的过程中，对于每个元素，有两种选择：
  - 将当前元素与之前的子数组和pre相加，形成一个新的子数组和。
  - 只考虑当前元素，形成一个新的子数组和。
- 选择这两种子数组和中的较大者作为新的pre。
结果记录：
- 在遍历过程中，记录pre中的最大值，即当前找到的最大子数组和。
- 最终返回这个最大值。