连续子数组的最大和-蒲公英云

连续子数组的最大和

Bertha 。 2023-10-01 09:22 51阅读 0赞

题目内容：
watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16

解题思路：

最重要的一点 ——更新，不管利用那种方法，都需要不断的更新
我选择的解法是，不断地更新max和nums[i]
更新nums[i]的目的也很明确，为了确定，我之前的和是否是到目前为止最大还是最小的就和nums[i]进行判断，若是num[i]比之前的和还要大，那就从nums[i]开始重新计算最大和，反之，就说明前面的和确实是最大的，就将nums[i]加上，并且更新max
max的更新，也很重要，如果是加上比之前的还小，那么就不更新，反之才更新

解题代码：

class Solution {
    public int maxSubArray(int[] nums) {
        //定义最大值为第一个元素
        int max = nums[0];
        //进行循环，对于这道题目来说，只有两种可能，要么大，要么小
        for(int i = 1;i < nums.length;i++){
            //如果nums[i] 小于 nums[i] + nums[i - 1]
            //就让nums[i] = nums[i] + nums[i - 1]
            //反之，舍弃之前的和，既然，和都没我一个nums[i]大，最大和自然也不是前面的，就让max从i下标的元素开始，重新计算，循环遍历
            if(nums[i] < nums[i - 1] + nums[i]){
                nums[i] = nums[i] + nums[i - 1];
            }
            /*
            1.如果是最大的和，自然是为了求得最大的子数组的和
            2.如果不是，就是重新计算和的开始
            */
            max = Math.max(nums[i],max);
        }
        return max;
    }
}