力扣Java - 53. 最大子数组和

力扣算法 - 最大子数组和

• 题目描述
• 示例演示
• • • • 示例一
      • 示例二
      • 示例三
• 算法代码
• 实现思想
• 代码解释

题目描述

• 一个整数数组 nums 。
• 找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
• 子数组是数组中的一个连续部分。

示例演示 示例一

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

示例二

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

示例三

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

算法代码

class Solution {
    public int maxSubArray(int[] nums) {
        int pre = 0,maxSum = nums[0];
        for(int num : nums){
            pre = Math.max(pre + num,num);
            maxSum = Math.max(maxSum,pre);
        }
        return maxSum;
    }
}

实现思想

• 子数组由0个元素不断壮大。
• 如果遇到当前数组元素加入子数组后，子数组和小于当前数组元素值，说明当前子数组中存在较多的负数，可以舍弃掉当前子数组，创建新的子数组，当前数组元素作为第一个元素加入，继续进行壮大 *** 作。

代码解释

• pre变量用于记录当前子数组中的元素和，初始子数组为空，初始值自然也应该为0。
• maxSum变量用于记录最大和。
• 首先默认第一个元素是当前最大的值，并将其赋值给maxSum变量。
• 使用增强for循环依次获得数组元素，并赋值给num变量。
• 从前往后依次执行“+” *** 作，将“pre+num”和“num”中的较大值赋值给pre变量。
• 如果“pre+num”值更大，则说明这个子数组还可以继续壮大。
• 如果“num”值更大，则说明可以结束当前子数组壮大 *** 作，创建新的子数组。
• 每遍历一次，都需要将maxSum变量值更新，最后的值即为所求。