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

算法的学习笔记—连续子数组的最大和

article 2024/11/19 14:32:16

😀前言
在算法问题中，求解连续子数组的最大和是一个经典问题。给定一个整数数组，找到一个连续的子数组，使得其元素之和最大。本文将详细讲解如何解决这个问题，并提供Java实现代码。

🏠个人主页：尘觉主页

文章目录

🥰连续子数组的最大和
- 😀问题描述
- 😊解题思路
- 💞Java实现
- 😊代码详解
- - 💞复杂度分析
- 😄总结

🥰连续子数组的最大和

😀问题描述

我们有一个整数数组，例如 {6, -3, -2, 7, -15, 1, 2, 2}。在这个数组中，连续子数组的最大和为 8（从第0个元素到第3个元素）。

😊解题思路

这个问题可以使用动态规划的思路来解决。具体来说，我们可以通过遍历数组并在遍历的过程中计算出当前子数组的和。如果当前子数组的和是负数，那么我们就从下一个元素重新开始计算子数组的和；否则，我们继续累加当前的元素值。同时，我们在遍历的过程中，不断更新最大子数组和的值。

步骤总结：

初始化两个变量：greatestSum 用来存储当前最大的子数组和，sum 用来存储当前子数组的和。
遍历数组中的每个元素：
- 如果当前的 sum 为负数，重新开始计算，即将当前元素赋值给 sum；
- 否则，将当前元素的值累加到 sum 中。
- 在每次累加后，更新 greatestSum，确保它始终是最大子数组和。
遍历完成后，greatestSum 就是所求的连续子数组的最大和。

💞Java实现

下面是使用上述思路的Java代码实现：

public int FindGreatestSumOfSubArray(int[] nums) {
    // 检查输入数组是否为空或者长度为零
    if (nums == null || nums.length == 0)
        return 0;
    
    // 初始化最大子数组和为负无穷大
    int greatestSum = Integer.MIN_VALUE;
    
    // 初始化当前子数组的和为0
    int sum = 0;
    
    // 遍历数组中的每一个元素
    for (int val : nums) {
        // 如果当前子数组的和为负数，则从当前元素重新开始计算
        sum = sum <= 0 ? val : sum + val;
        
        // 更新最大子数组和
        greatestSum = Math.max(greatestSum, sum);
    }
    
    // 返回最大子数组和
    return greatestSum;
}

😊代码详解

数组为空检查：首先，检查输入的数组是否为空或长度为零。如果是，则直接返回0，避免出现空指针异常。
初始化最大子数组和：我们将 greatestSum 初始化为 Integer.MIN_VALUE，这是为了确保即使数组中的所有元素都是负数，我们也能够正确地计算出最大子数组和。
遍历数组：在遍历数组时，我们根据当前子数组的和是否为负数，决定是否重新开始计算子数组的和。如果当前的 sum 是负数，那么直接将 val 赋值给 sum，否则将 val 累加到 sum 中。
更新最大和：每次更新 sum 后，我们使用 Math.max() 方法来更新 greatestSum，确保它总是最大子数组和。