53.最大子数组和

题目:53.最大子数组和

给你一个整数数组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 <= 10^5
-10^4 <= nums[i] <= 10^4

思路

1. 初始化:
   • currentSubArrayNum 用于记录当前子数组的和，初始化为数组的第一个元素。
   • maxSubArrayNum 用于记录最大子数组的和，初始化为数组的第一个元素。
2. 遍历数组:
   • 从数组的第二个元素开始遍历，更新 currentSubArrayNum 为当前元素和 currentSubArrayNum + 当前元素 中的较大值。
   • 更新 maxSubArrayNum 为 maxSubArrayNum 和 currentSubArrayNum 中的较大值。
3. 返回结果:
   • 最后，maxSubArrayNum 中保存的就是具有最大和的连续子数组的和。

• 时间复杂度:O(n)
• 空间复杂度:O(1)

代码

public int maxSubArray(int[] nums) {
    // 初始化当前子数组和为数组的第一个元素
    int currentSubArrayNum = nums[0];
    // 初始化最大子数组和为数组的第一个元素
    int maxSubArrayNum = nums[0];
    // 从第二个元素开始遍历数组
    for (int i = 1; i < nums.length; i++) {
        // 更新当前子数组和
        currentSubArrayNum = Math.max(currentSubArrayNum + nums[i], nums[i]);
        // 更新最大子数组和
        maxSubArrayNum = Math.max(currentSubArrayNum, maxSubArrayNum);
    }
    return maxSubArrayNum;
}