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 = [0]

输出：0

示例4:

输入：nums = [-1]

输出：-1

示例5:

输入：nums = [-100000]

输出：-100000

提示：

1 <= nums.length <= 3 * 10^4

-10^5 <= nums[i] <= 10^5

分析过程

定义最大子序和res，初始设置为数组nums的第一个元素。

定义子序和sum，用来保存遍历数组nums的过程中的子序和。

遍历数组nums，子序和sum累加数组nums的元素。

当子序和sum小于等于0时，设置子序和sum为当前元素。

因为前面部分的和为0，所以总和 = 0 + 当前元素 = 当前元素。

每次遍历，子序和sum都与最大子序和res比较，更新最大子序和res为较大值。

遍历结束后，最终得出最大子序和res。

解答代码

class Solution {
    public int maxSubArray(int[] nums) {
        // 定义初始最大和，用数组nums的第一个元素作为初始最大和
        int res = nums[0];

        // 定义计算过程的最大和
        int sum = 0;

        // 遍历数组nums
        // 逐个元素叠加出sum值，当sum小于等于0时，重置sum为当前元素，因为前面部分的和为0，计算总和时等于0加当前元素，即为当前元素
        for (int num : nums) {
            if (sum > 0) {
                // 若sum大于0，继续叠加
                sum += num;
            } else {
                // 若sum小于等于0，重置sum为当前元素
                sum = num;
            }
            
            if (sum > res) {
                // 更新最大和
                res = sum;
            }
        }

        return res;
    }
}

提交结果

执行用时1ms，时间击败95.48%的用户，内存消耗38.5MB，空间击败20.07%的用户。

运行结果

原文链接

原文链接：最大子序和