前言

-🏀大家好，我是BXuan，热爱编程与篮球的软件工程大二学生一名 -📚当爱上Coding&&Studying的那一刻… -🏃放弃不难，但坚持一定很酷。

🏆剑指 offer 42.连续数组的最大子数和

🔊问题描述：

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

🏀输入输出示例：

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

🎱提示：

1 <= arr.length <= 10^5 -100 <= arr[i] <= 100

🥇代码示例：

class Solution {
          
   
    public int maxSubArray(int[] nums) {
          
   
        //动态规划
        //为什么刚开始要定义res=nums[0]呢？
        //因为如果只有一个元素的话，需要返回的就是该值，而不是0或者其他的。
        int res = nums[0];
        int sum = 0;
        //对数组进行遍历
        for(int num : nums){
          
   
        	//这一步其实就是在判断，当后面的数使得整体和减小的时候，果断舍弃。
        	//寻找下一个使和增大的数，即实现了滑动窗口。
            sum = Math.max(sum+num, num);
            res = Math.max(sum, res);
        }
        return res;
    }
}

🔑解题思路

本题就是一个简单的动态规划的问题，那么如何得到最优解呢？ 首先就是对题目的理解，题目的意思就是得到连续的最大的子数组和，那么首先需要对每个数字进行判断，加上这个数字之后能变大或者减小(减小的情况肯定是该数是小于0的数)，然后去比较大小，然后对结果进行重新比较赋值即可。